Лучшая версия для возврата

int result = 0, n;
int task[1000][2];

//Checks if task overlaps with the time range [t1, t2]
bool taskFit(int &taskno, int &t1, int &t2){
if(task[taskno][1] &lt t1)return false;
else if(task[taskno][0] > t2)return false;
else return true;
}

void backtrack(int t1, int t2, int t3, int t4, int taskno, int grp1, int grp2){
//t1, t2 represultent time bounds for group1
//t3, t4 represultent time bounds for group2
//grp1: number of tasks that can be performed in time range of group1
//grp2: number of tasks that can be performed in second time stamp

result = max(grp1 + grp2, result);
if(result==n || taskno==(n+1))return;

//putting task in first group if it fits in the range of group1
if(taskFit(taskno, t1, t2))
backtrack(max(t1, task[taskno][0]), min(t2, task[taskno][1]), t3, t4, taskno+1, grp1+1, grp2);

//putting task in second group if it fits in its range
if(taskFit(taskno, t3, t4))
backtrack(t1, t2, max(t3, task[taskno][0]), min(t4, task[taskno][1]), taskno+1, grp1, grp2+1);

//simply ignoring the task
backtrack(t1, t2, t3, t4, taskno+1, grp1, grp2);
}

main(){
//...we have the value of n and time range of all n tasks
// for ith task time range in obtained as [task[i][0], task[i][1]]

//initially both groups are set in time range = [0, 2000000000]

//here we put the task1 in first group
//thus setting the new range for group 1
backtrack(task[0][0], task[0][1], 0, 2000000000, 2, 1, 0);

//ignoring the first task, the group ranges remain as it is
backtrack(0, 2000000000, 0, 2000000000, 2, 0, 0);
}

Я объясню алгоритм, который (я думаю) должен иметь N³ сложность времени, а N² сложность памяти (N — количество задач). Я постараюсь описать, откуда это & как это работает в первую очередь, но вы можете перейти к концу, если вы просто хотите псевдокод.

Во-первых, я хотел бы представить ваши входные данные в виде матрицы (или «каракули»). Если я возьму подмножество из вашего примера:

+--------+---+---+---+---+---+---+---+---+---+----+----+----+
|        | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
+--------+---+---+---+---+---+---+---+---+---+----+----+----+
| Task 1 | X | X | X | X | X |   |   |   |   |    |    |    |
| Task 2 |   |   | X | X |   |   |   |   |   |    |    |    |
| Task 3 |   |   |   |   | X | X |   |   |   |    |    |    |
| Task 4 |   |   |   |   |   |   | X | X | X | X  | X  | X  |
+--------+---+---+---+---+---+---+---+---+---+----+----+----+

В настоящее время ваши данные индексируются по строке: task[taskIndex] // --> time interval of this task, Что произойдет, если мы переиндексируем по столбцам: availableTasks[timeIndex] // --> set of tasks that can be executed at this time?

При наивной реализации этой структуры данных мы могли бы написать следующий наивный алгоритм (в псевдо-C ++):

int MAX_TIME = 2000000000; // 2,000,000,000
// reindexed input
std::unordered_set<int>; availableTasks[MAX_TIME];
// main algorithm
int bestTotal = -1; // result
int r1, r2; // time values to get bestTotal
// brute force: try all pair of time values:
for (int t1 = 0; t1 <= MAX_TIME-1; t1++) {
for (int t2 = t1; t2 <= MAX_TIME; t2++) {
int count = union(availableTasks[t1], availableTasks[t2]).size();
if (count > bestCount) {
r1 = t1; r2 = t2;
bestCount = count;
}
}
}

Хорошие новости: сложность времени больше не экспоненциальная! Плохие новости:

1. Огромное использование памяти: из-за стоимости MAX_TIME, availableTasks будет несколько ГБ даже с несколькими задачами.
2. Смешное время выполнения: двойной цикл примерно 2 * 10¹⁸ итераций. На процессоре 4 ГГц с 1 итерацией / циклом (чрезвычайно оптимистично) это более десяти лет.

Таким образом, любое практическое решение не может использовать грубую силу во всех парах значений времени.

Давайте рассмотрим простой случай с двумя задачами:

• Задача 0: [1; 1 499 999]
• Задача 1: [500 000; 1 999 999]

Интуитивно, вы бы сказали, что нет необходимости тестировать 2 000 000 временных значений. Вы должны учитывать, что существует 4 интервала значений времени (исключая верхнюю границу):

• Интервал А: [1; 500 000 [
• Интервал B: [500 000; 1 500 000 [
• Интервал C: [1 500 000; 2 000 000 [
• Интервал D: [2 000 000; MAX_TIME [

Если Ta а также Tb выбраны в тот же интервал, мы имеем availableTasks[Ta] == availableTasks[Tb], Таким образом, в основном, мы просто должны проверить одно временное значение в каждом интервале. Я выберу нижнюю границу для представления каждого интервала: 1 | 500 000 | 1 500 000 | 2000000.

_{Примечание: по математике мы разделение набор значений времени, определяя отношение эквивалентности : t1~t2 <=> availableTasks[t1] == availableTasks[t2], затем выбирая репрезентативный элемент из каждого класса эквивалентности.}

Откуда эти репрезентативные ценности? Легко:

tasks[0][0] // 1
tasks[1][0] // 500,000
tasks[0][1] + 1 // 1,500,000
tasks[1][1] + 1 // 2,000,000

Правило ограничения первого кандидата: Мы обязательно найдем оптимальное решение, если протестируем все пары в наборе S={tasks[*][0], tasks[*][1]+1},

Это уже должно ограничить достаточное количество значений, чтобы заставить алгоритм работать в разумные сроки, но мы можем сделать это проще и быстрее. Значения в предыдущем наборе можно интерпретировать следующим образом:

1. t=tasks[k][0]: задача k не может быть выполнена в предыдущем интервале (заканчивается в t-1), но может выполняться в интервале, начинающемся с t
2. t=tasks[k][1]: задача k может быть выполнена в предыдущем интервале (заканчивается в t-1), но не может быть выполнен в интервале в t

С этой точки зрения интервал, начинающийся с t в случае 2 бесполезный кандидат: если нет l проверка tasks[l][0] == tasks[k][1]+1 (имеется в виду, что в момент времени t существует другая задача, которая становится исполняемой, поэтому t также падает в случае 1), любое значение времени в предыдущем интервале является лучшим кандидатом (поскольку availableTasks[t-1] строго содержит availableTasks[t]). Следовательно:

Правило ограничения лучшего кандидата: Мы обязательно найдем оптимальное решение, если протестируем все пары в наборе S={tasks[*][0]},

Генерация переиндексированных входных данных:

int n = 1000; //number of tasks
// availableTasks[timeIndex] : set of tasks executable at timeIndex.
// Only candidate values are stored in the map.
std::map<int, std::unordered_set<int>> availableTasks;
for ( timeCandidate : task[*][0] ) {
auto& set = availableTasks[timeCandidate];
for ( int taskIndex = 0; taskIndex < n; taskIndex++) {
if (timeCandidate in task[taskIndex]) {
set.insert(task);
}
}
}

Основной алгоритм:

int bestTotal = -1; // result
int r1, r2; // time values to get bestTotal
auto& map = availableTasks; // alias
for (auto it1=map.begin(); it1 != map.end(): it1++) {
int t1 = it1->first;
auto& set1 = it1->second;
auto it2 = it1; // copy the iterator
it2++;
for (; it2 != map.end(); it2++) {
int t2 = it2->first;
auto& set2 = it2->second;
// assuming here that union().size() can be computed in O(n) time.
int count = union(set1, set2).size();
if (count > bestCount) {
r1 = t1; r2 = t2;
bestCount = count;
}
}
}

Если этот алгоритм работает, я думаю, что возможно было бы уточнить его с точки зрения пространственного & сложность времени. Но этот пост уже довольно длинный ^^. Во-первых, я предлагаю вам проверить, что это правильно и соответствует ли оно вашим требованиям к производительности.