Дано множество отрезков (a_i, b_i) на прямой. Найти список интервалов этой прямой, которые покрываются одновременно наибольшим кол-вом заданных отрезков. Решение должно иметь сложность O(n*log(n)). Подсказка: надо составить список из границ отрезков (класс, содержащий значение и признак того, является ли данное значение началом или концом отрезка). Затем этот список упорядочить (вначале по значению, при одинаковом значении концы отрезков должно оказаться раньше начал). Далее проходим по отсортированному списку, начало интервала - +1 к кол-ву интервалов, окончание - -1. Как только кол-во интервалов становится больше уже найденного, сбрасываем результирующий список интервалов и начинаем формировать заново.
Сортировка O(nlog(n)) + проход по списку O(n) = O(nlog(n) + n) = O(n*log(n)).
Релизованы с помощью JUnit