Я объясню алгоритм, который (я думаю) должен иметь N 3 сложность времени и N 2 сложность памяти (N - количество задач).Я постараюсь описать, откуда он исходит и как он работает в первую очередь, но вы можете перейти к концу, если вам нужен только псевдокод.
Шаг 1: Переиндексировать ваши входные данные
СначалаЯ хотел бы представить ваши входные данные в виде матрицы (или "каракули").Если я возьму подмножество из вашего примера:
+--------+---+---+---+---+---+---+---+---+---+----+----+----+
| | 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;
}
}
}
Хорошоновость: сложность времени больше не экспоненциальная!Плохие новости:
- Огромное использование памяти: из-за значения
MAX_TIME, availableTasks будет несколько ГБ даже при небольшом количестве задач. - Смешное время выполнения: двойной циклиметь примерно 2 * 10 18 итераций.На процессоре 4 ГГц с 1 итерацией / циклом (чрезвычайно оптимистично) это более десяти лет.
Таким образом, любое практическое решение не может использовать грубую силу для всех пар значений времени.
Шаг2: ограничить кандидатов на временные значения.
Давайте рассмотрим простой случай с 2 задачами:
- Задача 0: [1; 1 499 999]
- Задача 1:[500 000;1 999 999]
Интуитивно, вы бы сказали, что нет необходимости проверять 2 000 000 значений времени.Вы бы посчитали, что существует 4 интервала значений времени (исключая верхнюю границу):
- Интервал A: [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 |2 000 000.
Примечание. В математических терминах мы разбиваем набор значений времени, определяя отношение эквивалентности : 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}.
Это должноУже достаточно ограничить значения, чтобы алгоритм работал в разумные сроки, но мы можем сделать это проще и быстрее.Значения в предыдущем наборе можно интерпретировать следующим образом:
t=tasks[k][0]: задача k не может быть выполнена в предыдущем интервале (заканчивающемся на t-1), но может быть выполнена в этом интерваленачиная с tt=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]}.
Алгоритм (непроверенный, псевдоC ++)
Генерация переиндексированных входных данных:
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;
}
}
}
Если этот алгоритм работает, я думаю, что можно было бы уточнить его в дальнейшемУсловия пространственной и временной сложности.Но этот пост уже довольно длинный ^^.Сначала я предлагаю проверить, правильно ли это, и соответствует ли оно вашим требованиям к производительности.