0

This code returns the overlap coordinates. Example: for input of [10, 30] [20, 50] [40, 70,] [60, 90] [80, 100] The answer should be: [20, 30], [40, 50] [60, 70] [80,90] Is there a way to solve this problem in less than quadratic time complexity ?

Thanks,

  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;
}
Don Roby
  • 40,677
  • 6
  • 91
  • 113
JavaDeveloper
  • 5,320
  • 16
  • 79
  • 132

1 Answers1

0

You should be able to reduce this to O(NlogN) by sorting the interval array (ordered by the interval start-points) and then iterating over it comparing successive intervals.

I doubt that it is possible to do better that O(NlogN) unless you can amortize the cost of the sorting step over multiple runs.

Note that this general approach will work if one interval can overlap more than one other interval. But if you want to enumerate each of the overlaps, then in the worst case there can be O(N^2) overlaps, and hence the algorithm has to be O(N^2).

(For example, in "[1,2], [1,2], [1,2], [1, 2]" each interval overlaps all of the others giving 6 overlaps ... or 12 if you don't eliminate symmetric pairs.)

Stephen C
  • 698,415
  • 94
  • 811
  • 1,216