Если все интервалы отсортированы по начальной точке, то легко проверить, перекрываются ли два из них. Просто просмотрите все интервалы, сохраните максимальную конечную точку, которую мы получили из предыдущих интервалов, и если максимальная конечная точка> текущая начальная точка, то мы получили перекрытие. Если у нас не было перекрытия для всех интервалов, то перекрытия нет.
Если интервалы не отсортированы. Тогда в общем случае нижняя граница для обнаружения перекрытия составляет O (n logn). Потому что, когда все интервалы имеют start_point = end_point, тогда проблема сводится к проблеме четкости. http://en.wikipedia.org/wiki/Element_distinctness_problem. Все алгоритмы сравнения требуют времени O (n log n).
Однако, если точки всех интервалов являются дискретными и находятся в некотором определенном диапазоне [0, L), например, количество секунд в дне составляет от 0 до 60 * 60 * 24, тогда оно может быть решено в O (n + L) линейном времени и O (L) пространстве.
Идея состоит в том, что каждый интервал i имеет начальную точку si и конечную точку ei. Мы создаем массив a = new int [L]. Для каждого интервала i мы добавляем 1 для a [si] к [ei]. Затем мы проверяем, существует ли a [j]> 1, если это так, мы получаем перекрытие.
Самый наивный метод - использовать 2 для циклов, а временная сложность составляет O (n * L). В программировании Peals есть умный алгоритм, который может сократить время работы до O (n + L). Если вам интересно, и именно этого хочет ваш интервьюер, я могу показать вам детали.
Итак, это 3 ситуации, которые я знаю. Какой из них, по вашему мнению, соответствует вашей проблеме?