Вот реализация O(N lg N) в Java, которая расширяет ответ, предоставленный @Nikita Rybak.
Мое решение находит каждый интервал, который перекрывается хотя бы с одним другим интервалом, и считает их оба как перекрывающиеся интервалы.Например, два интервала (1, 3) и (2, 4) из исходного вопроса ОП перекрывают друг друга, и поэтому в этом случае имеются 2 перекрывающихся интервала.Другими словами, если интервал A перекрывается с интервалом B, то я добавляю и A и B к результирующему набору интервалов, которые перекрываются.
Теперь рассмотрим интервалы (1, 100), (10, 20) и (30, 50).Мой код обнаружит, что:
[ 10, 20] overlaps with [ 1, 100]
[ 30, 50] overlaps with [ 1, 100]
Resulting intervals that overlap with at least one other interval:
[ 1, 100]
[ 30, 50]
[ 10, 20]
Чтобы предотвратить двойной подсчет (1, 100), я использую Java Set, в котором хранятся только уникальные объекты Interval.
Мое решение следуетэтот контур.
- Сортировка всех интервалов по начальной точке.Этот шаг
O(N lg N). - Отслеживать
intervalWithLatestEnd, интервал с последней конечной точкой. - Итерировать по всем интервалам в отсортированном списке.Если интервал перекрывается с
intervalWithLatestEnd, добавьте оба к набору.Обновите intervalWithLatestEnd при необходимости.Это шаг O(N). - Возвращение набора (и преобразование в список при необходимости).
Общее время работы O(N lg N).Требуется выходной набор размера O(N).
Реализация
Чтобы добавить интервалы в набор, я создал собственный класс Interval, который переопределяет equals(), как и ожидалось.
class Interval {
int start;
int end;
Interval(int s, int e) {
start = s; end = e;
}
@Override
public String toString() {
return String.format("[%3d, %3d]", start, end);
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + start;
result = prime * result + end;
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
final Interval other = (Interval) obj;
if (start != other.start)
return false;
if (end != other.end)
return false;
return true;
}
}
А вот код, который запускает алгоритм:
private static List<Interval> findIntervalsThatOverlap(List<Interval> intervals) {
// Keeps unique intervals.
Set<Interval> set = new HashSet<Interval>();
// Sort the intervals by starting time.
Collections.sort(intervals, (x, y) -> Integer.compare(x.start, y.start));
// Keep track of the interval that has the latest end time.
Interval intervalWithLatestEnd = null;
for (Interval interval : intervals) {
if (intervalWithLatestEnd != null &&
interval.start < intervalWithLatestEnd.end) {
// Overlap occurred.
// Add the current interval and the interval it overlapped with.
set.add(interval);
set.add(intervalWithLatestEnd);
System.out.println(interval + " overlaps with " +
intervalWithLatestEnd);
}
// Update the interval with latest end.
if (intervalWithLatestEnd == null ||
intervalWithLatestEnd.end < interval.end) {
intervalWithLatestEnd = interval;
}
}
// Convert the Set to a List.
return new ArrayList<Interval>(set);
}
Контрольные примеры
Вот контрольный пример, в котором выполняются исходные интервалы OP:
public static void testcase() {
List<Interval> intervals = null;
List<Interval> result = null;
intervals = new ArrayList<Interval>();
intervals.add(new Interval(1, 3));
intervals.add(new Interval(12, 14));
intervals.add(new Interval(2, 4));
intervals.add(new Interval(13, 15));
intervals.add(new Interval(5, 10));
result = findIntervalsThatOverlap(intervals);
System.out.println("Intervals that overlap with at least one other interval:");
for (Interval interval : result) {
System.out.println(interval);
}
}
с результатом:
[ 2, 4] overlaps with [ 1, 3]
[ 13, 15] overlaps with [ 12, 14]
Intervals that overlap with at least one other interval:
[ 2, 4]
[ 1, 3]
[ 13, 15]
[ 12, 14]
Наконец, вот более сложный тестовый пример:
public static void testcase() {
List<Interval> intervals = null;
List<Interval> result = null;
intervals = new ArrayList<Interval>();
intervals.add(new Interval(1, 4));
intervals.add(new Interval(2, 3));
intervals.add(new Interval(5, 7));
intervals.add(new Interval(10, 20));
intervals.add(new Interval(15, 22));
intervals.add(new Interval(9, 11));
intervals.add(new Interval(8, 25));
intervals.add(new Interval(50, 100));
intervals.add(new Interval(60, 70));
intervals.add(new Interval(80, 90));
result = findIntervalsThatOverlap(intervals);
System.out.println("Intervals that overlap with at least one other interval:");
for (Interval interval : result) {
System.out.println(interval);
}
}
с результатом:
[ 2, 3] overlaps with [ 1, 4]
[ 9, 11] overlaps with [ 8, 25]
[ 10, 20] overlaps with [ 8, 25]
[ 15, 22] overlaps with [ 8, 25]
[ 60, 70] overlaps with [ 50, 100]
[ 80, 90] overlaps with [ 50, 100]
Intervals that overlap with at least one other interval:
[ 2, 3]
[ 8, 25]
[ 9, 11]
[ 50, 100]
[ 1, 4]
[ 15, 22]
[ 10, 20]
[ 60, 70]
[ 80, 90]