9
\$\begingroup\$

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;
}
\$\endgroup\$
11
\$\begingroup\$

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();
}
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – bowmore Aug 25 '13 at 8:23
  • \$\begingroup\$ In that case I would annotate intervals with @Nonnull and let FindBugs point out bad calls. \$\endgroup\$ – David Harkness Aug 25 '13 at 8:28
  • \$\begingroup\$ That assumes you control all possible clients. The annotation is fine, but any well behaved function should reject illegal input. \$\endgroup\$ – bowmore Aug 25 '13 at 8:34
  • 1
    \$\begingroup\$ @bowmore - Well behaved functions should tolerate poorly behaved clients if they can instead of unnecessarily throwing exceptions at runtime. \$\endgroup\$ – David Harkness Aug 25 '13 at 21:13
  • 1
    \$\begingroup\$ Responding with valid output to illegal input will only lead to bugs that are harder to detect, so : fail fast \$\endgroup\$ – bowmore Aug 25 '13 at 21:25
6
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.