Here's an O(N lg N) implementation in Java that extends the answer provided by @Nikita Rybak.
My solution finds every interval that overlaps with at least one other interval and counts them both as overlapping intervals. For example, the two intervals (1, 3) and (2, 4) from OP's original question overlap each other, and so in this case there are 2 overlapping intervals. In other words, if interval A overlaps with interval B, then I add both A and B to the resulting set of intervals that overlap.
Now consider the intervals (1, 100), (10, 20) and (30, 50). My code will find that:
[ 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]
In order to prevent (1, 100) from being counted twice, I use a Java Set that keeps only unique Interval objects.
My solution follows this outline.
- Sort all intervals by starting point. This step is
O(N lg N).
- Keep track of
intervalWithLatestEnd, the interval with the latest end point.
- Iterate over all the intervals in the sorted list. If an interval overlaps with
intervalWithLatestEnd, then add both to a Set. Update intervalWithLatestEnd when needed. This step is O(N).
- Return the Set (and convert to a List if needed).
The total running time is O(N lg N). It requires an output Set of size O(N).
Implementation
In order to add intervals to a set, I created a custom Interval class that override equals(), as expected.
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;
}
}
And here is the code that runs the algorithm:
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);
}
Test cases
Here is a test case that runs the OP's original intervals:
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);
}
}
with the result:
[ 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]
Finally, here is a more advanced test case:
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);
}
}
with the result:
[ 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]
