Find intersections of overlapping intervals

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 getOverlap(List intervalList) {
    if (intervalList == null) {
        throw new NullPointerException("Input list cannot be null.");
    }

    final HashSet hashSet = new HashSet();

    for (int i = 0; i  intervali.getStart() && i != j) {
                hashSet.add(new OverlapCoord(Math.max(intervali.getStart(),intervalj.getStart()), 
                                             Math.min(intervali.getEnd(), intervalj.getEnd())));
            }
        }
    }

    return hashSet;
}

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.emptySet();
}

StackExchange Code Review Q#30190, answer score: 11