Combining intersecting intervals

Question

Possible Duplicate:
Union of intervals
how to overlap intervals efficiently

Given a list of intervals say all integers, it should be possible to collapse them into one interval if they do intersect or overlap otherwise the given intervals remain unaffected. Say, if the input is e.g.I [(2-6), (1-4), (8-12)], the expected output is [(1-6), (8-12)] e.g. II [(4-7), (2-6), (1-4), (8-12), (7-9)] the expected output is [(1-12)].

Correction: Missed the sorting part, so yes, it is a O(nlogn) time NOT O(n). Thanks for pointing that out. I have written and tested a O(nlogn) time and O(2n) space algorithm approach that works. Sharing the code of this approach below. I am interested in hearing different approaches to solving this problem, possibly more efficient.

//Assuming each of the intervals, (2-6) and so on are represented as "Interval" objects (class definition shown below), where low = 2 and high = 6 // Step1: Sort by the low endpoint of the given intervals // Step2: find Union of the sorted intervals

//Input:

List<Interval> intervalList = new ArrayList<Interval>();

//Output:

List<Interval> unionList = new ArrayList<Interval>();    

private static final Comparator<Interval> Low_EPSorter = new LowEPSorter();

class Interval {
  int low, high;

  Interval(int l, int h, int m) {
    low = l;
    high = h;
  }
}

////-------BEGIN: Method which finds the Union Of given intervals ----//////

void UnionOfIntervals() {
  //Find intersection and combine intervals as necessary
  int sz = intervalList.size();

  // sort by low endpoint
  Collections.sort(intervalList, Low_EPSorter);

      for(int i = 0; i < sz; i++) {
        int j = i;
        if(j > 0) {
          if( Intervals.intersect(intervalList.get(j), intervalList.get(j-1)) ) {
            Interval v = union(intervalList.get(j), intervalList.get(j-1));
            checkAndAdd(v, unionList);
          }
          else {
            if(i == 1) {
              unionList.add(intervalList.get(j-1));
              unionList.add(intervalList.get(j));
          }
          else {
            unionList.add(intervalList.get(j));
          }
        } //No intersection
      } //If 2 elements atleast
      }

      //Print intervals after union
      System.out.println("Input intervals after sorting:");
      for(Interval v : intervalList) {
        System.out.print(v.low + "," + v.high + " ");
      }
      System.out.println();
      System.out.println("Union of intervals:");
      for(Interval v : unionList) {
        System.out.print(v.low + "," + v.high + " ");
      }
    }

    void checkAndAdd(Interval x, List t) {
      int top = t.size()-1;
      if( top >=0 && Intervals.intersect(unionList.get(top), x) ) {
        Interval v = union(unionList.get(top), x);
        t.remove(top);
        t.add(v);
      }
      else {
        t.add(x);
      }
    }

////-------END: Method which finds the Union Of given intervals ----//////

////--- helper methods --- ////

static boolean intersect(Interval a, Interval b) {
      boolean r = false;
      if(b.high < a.low || b.low > a.high)
        r = false;
      else if(a.low <= b.high && b.low <= a.high)
        r = true;
      return r;
}

Interval union(Interval a, Interval b) {
      int l = (a.low < b.low) ? a.low : b.low;
      int max = (a.high > b.high) ? a.high : b.high;
      return new Interval(l, max);
}

private static class LowEPSorter implements Comparator<Interval> {

      public int compare(Interval a, Interval b) {
        int r = 0;
        if(a.low < b.low)
          r = -1;
        else if(a.low > b.low)
          r = 1;
        return r;
      }

}

My java experience is not the best, but your due to http://docs.oracle.com/javase/1.4.2/docs/api/java/util/Collections.html#sort(java.util.List, java.util.Comparator) you haven't written an algorithm that runs in O(n), but O(n * log n) instead — citronas, Sep 10 '12 at 17:10
-1 for not researching and not paying attention to the suggested duplicates SO provided while entering this question. This has been answered multiple times on SO — Jim Garrison, Sep 10 '12 at 17:23
can be solved in O(n) but highest number in the interval should be comparable to n. — Akashdeep Saluja, Sep 10 '12 at 17:25
@AkashdeepSaluja: Can be solved in O(n) is, if a non-comparison based sorting is choosen like counting sort where knowledge of highest number in the input helps? — sangv, Sep 11 '12 at 18:09
@sangv yeah can say that the idea is basically of count sort but not exactly.Also i have posted my suggestion as an answer. — Akashdeep Saluja, Sep 11 '12 at 19:23

score 1 · Accepted Answer · answered Sep 11 '12 at 19:21

Take a array of size n ( where n is the largest number ) and fills the interval start and end with 1 and -1 respectively.

By this I mean if the intervals are

{[1-4],[6-8]}

Then the array elements would be like

array[1]=1,array[4]=-1,array[6]=1,array[8]=-1

and the rest all other locations of array would be set to zero.

Now traverse the array and by scanning the array we can get the intervals, like for the case

{[1-4],[2-5],[7-9]},

first fill the array as stated above , the array A would look like(assuming the starting index be 1):

A=[1,1,0,-1,-1,0,1,0,1]

Now traverse the array A from beginning and take a variable sum=0 and add the value stored at location of array to sum.

Stating the sum at each index of array:

At location 1: sum = 1 ( 1 at index 1 )

At location 2: sum = 2 ( 1 at index 2 )

At location 3: sum = 2 ( 0 at index 3 )

At location 4: sum = 1 ( -1 at index 4 )

At location 5: sum = 0 ( -1 at index 5 )

Now the sum reaches to zero it means an interval ends here so the new interval will be [1-5]

At location 6: sum = 0 ( 0 at index 6 )

At location 7: sum = 1 ( 1 at index 7 )

(At location 7 the sum again becomes greater than zero it means an interval has just started)

At location 8: sum = 1 ( 0 at index 8 )

At location 9: sum = 0 ( -1 at index 9 )

Interval started at location 7 just ended so the new interval ranges would be

{[1-5],[7-9]}

Hope it helps.

FYI, this doesn't work with test case of (i.e., if you have dups): (-1, -1), (-1, -1), (3, 5), (6, 6), (3, 5) — kenyee, Sep 11 '13 at 23:23

score 0 · Answer 2 · answered Sep 10 '12 at 17:22

If you are looking for a more efficient algorithm than O(n) for this problem, I don't believe that you will find it. No matter what data structure you use for storing the initial interval values, your worst case scenario is that none of the intervals overlap and that you have to check each interval to confirm this, hence the O(n). Even with a HashMap and a very elaborate key structure, you are still looking at O(n).

With this being said, I'm not sure if any other approach is worth investigating as you have already found an algorithm that solves it in the best time possible, O(n).

This is of course, after the interval list has been sorted. – Jordan Ell Sep 10 '12 at 17:26 — Jordan Ell, Sep 10 '12 at 17:26

score 0 · Answer 3 · answered Sep 10 '12 at 17:23

Just an idea: manage a set of non-intersecting intervals. Starting from empty set, add incoming intervals. If new interval intersects with one or two existing intervals, combine them. To calculate intersections, use 2 TreeMaps referencing to the same set of intervals but by different keys: low and high bounds.

score 0 · Answer 4 · edited Sep 11 '12 at 08:20

0

Just another idea:

Use a Bool array
- make all the values false by default
- for all the intervals(in input) make the values true
- Scan the updated array and get the final intersected result.

edited Sep 11 '12 at 08:20

Mike Aski

9,180
4
46
63

answered Sep 10 '12 at 17:42

k53sc

6,910
3
17
21

or java.util.BitSet instead of boolean array, to save space. – Alexei Kaigorodov Sep 10 '12 at 18:23
This approach (array of Bool) is like plotting the intervals and scanning the plotted interval to find intersection. So, the Bool array(two dimensional) represents all possible intervals from min to max value (from the given intervals input) with only the input intervals set to true. This updated array upon scanning would give the final intersecting interval (if any) and non-intersecting intervals -- Is that right? – sangv Sep 11 '12 at 17:59

Combining intersecting intervals

4 Answers4