Учитывая набор временных интервалов, как найти максимальное количество перекрытий. Существует ли какой-либо алгоритм, который решает данную задачу с временной сложностью O (n log n) или O (n)?Максимальное количество перекрытий всех временных интервалов
пример: (6: 00-9: 30), (9: 00-12: 30), (10: 00-10: 30), (12: 00-14: 30), (11:00) -13: 30). Ответ 3
Сортировка значений с использованием быстрого сортировки - O(nlogn) времени.
6:00(+)
9:30(-)
9:00(+)
12:30(-)
10:00(+)
10:30(-)
12:14:30(Dude wut?) --> Im going to assume you meant 12:00(+) ,14:30(-)
11:00(+)
13:30(-)
Становится
6:00(+)
9:00(+)
9:30(-)
10:00(+)
10:30(-)
11:00(+)
12:00(+)
12:30(-)
13:30(-)
14:30(-)
итерацию по списку увеличивающимся для каждого плюс и декремента для каждого минуса, запишите максимальное значение, найденное. Это занимает O(n) Время
Общее время O(nlogn + n) = O(nlogn)
@gbtimmon, это потрясающий человек! благодаря – user2601967
Это зависит от многого. Если элемент перекрывает два разных набора, считается ли он одним перекрытием или двумя перекрытиями? Также, есть (12:14:30) правильно? Это временная метка? Это просто непоследовательно, учитывая другие наборы. – Firo
Не существует ли 4 временных перекрытия? Предполагается, что (12:14:30) должно быть (12: 00-14: 30) –
@Firo это опечатка, см. Отредактированную версию. – user2601967