Find intersections of overlapping intervals

Question

This code finds the intersections of all overlapping intervals.

Example: if [0-20], [15-40], and [25-50] are the 3 intervals then the output should be [15-20] and [25-40].

I could not find an answer with complexity less than \$O(n^2)\$. Please suggest a better solution if one exists. Additionally, assume the input intervals are sorted by their start times.

public static Set<OverlapCoord> getOverlap(List<Interval> intervalList) {
 if (intervalList == null) {
 throw new NullPointerException("Input list cannot be null.");
 }
 final HashSet<OverlapCoord> hashSet = new HashSet<OverlapCoord>();
 for (int i = 0; i < intervalList.size() - 1; i++) {
 final Interval intervali = intervalList.get(i);
 for (int j = 0; j < intervalList.size(); j++) {
 final Interval intervalj = intervalList.get(j);
 if (intervalj.getStart() < intervali.getEnd() && intervalj.getEnd() > intervali.getStart() && i != j) {
 hashSet.add(new OverlapCoord(Math.max(intervali.getStart(),intervalj.getStart()), 
 Math.min(intervali.getEnd(), intervalj.getEnd())));
 }
 }
 }
 return hashSet;
}

Answer 1

Because the intervals are already sorted by start time, you can begin the inner loop at j = i + 1 and simplify the if test and drop the call to max:

if (intervalj.getStart() < intervali.getEnd()) {
 hashSet.add(new OverlapCoord(intervalj.getStart(), 
 Math.min(intervali.getEnd(), intervalj.getEnd())));
}

However, is it possible for three intervals to overlap?

[===============]
 [=============]
 [=============]

If so, this will produce three overlaps:

 [=======]
 [==]
 [========]

Is this desired? What about if the first and third intervals above butted up against each other rather than overlapping themselves?

 [=======]
 [====]

Should all these cases be merged into the same single overlap?

 [=============]

Here are some better variable names to consider:

• intervalList -> intervals
• hashSet -> overlaps
• intervali -> leftInterval or lowerInterval
• intervalj -> rightInterval or upperInterval

I find it's best to leave the type of collection out of the name. First, it makes it easier to change later. And second, you can see it and in any IDE hover over the method to see the required type. I might even drop the Interval suffix from the last two above since this method only deals with intervals.

Finally, there's no reason this method couldn't accept a null list. It should respond just as it does when the list is empty: return an empty set.

if (intervals == null || intervals.isEmpty()) {
 return Collections.<OverlapCoord>emptySet();
}

• bowmore: Accpting null as valid input seems to be no more than tailoring to badly behaved clients. I would maintain IllegalArgumentException for null arguments, and simply fail fast.
• David Harkness: In that case I would annotate intervals with @Nonnull and let FindBugs point out bad calls.
• bowmore: That assumes you control all possible clients. The annotation is fine, but any well behaved function should reject illegal input.
• David Harkness: @bowmore - Well behaved functions should tolerate poorly behaved clients if they can instead of unnecessarily throwing exceptions at runtime.
• bowmore: Responding with valid output to illegal input will only lead to bugs that are harder to detect, so : fail fast

Answer 2

Sort the intervals by starting value, and length incremental : O(n sqrt(n))

Loop the intervals and check overlaps between current and previous one. : O(n)

Resulting complexity : O(n sqrt(n))

You said to assume they're already sorted, but I'm not sure whether they're also sorted by length, which is needed to better handle intervals that have the same starting value. If they're also already sorted by length, then you only have the loop to check overlaps between previous and current, which would leave you with O(n) complexity.