Finding elementary intervals in overlapping intervals

Question

I came across a good question while preparing for some programming interviews.

Given a set of possibly overlapping intervals, you need to write a function to return all elementary intervals among them. For example: if you are given intervals as the following list of pairs: {{1,5}, {3,10}, {5,11}, {15,18}, {16,20}}, then you need to return the following:

{{1,3}, {3,5}, {5,10}, {10,11}, {15,16}, {16,18}, {18,20}}

Note the following in the above answer:

• The interval {11,15} is omitted in the answer because it is non-existent in the input.
• The interval {1,5} from the input has been split up into {1,3}, {3,5} in the answer because of the starting point "3" defined in {3,10} in the input that cuts the interval into two elementary intervals.

Method signature in Java:

List<Pair<Integer, Integer>> generateElementaryIntervals(List<Pair<Integer, Integer> intervals)

One of the solutions that I imagined was to separate the input into non-intersecting sets, and then a simple O(NlogN) sort over all numbers in each non-intersecting set will yield the answer. Is there a more efficient way to do it?

Answer 1

You could break this problem up into nested intervals first, then deal with each nesting separately. By nested, I mean intervals that share at least one point. For the example you gave:

{{1,5}, {3,10}, {5,11}, {15,18}, {16,20}}

there are two nestings:

{1,5}, {3,10}, {5,11}

and

{15,18}, {16,20}

In general, to determine the nestings, you can sort the intervals based on the left endpoint (as in your example), then run through and start a new nesting whenever you see {x,y}, {x',y'} with y < x'.

For a nesting, the "elementary intervals" are formed by the sorted sequence (without repeats) of values. In the example, the nestings give

(1,3,5,10,11) -> {1,3}, {3,5}, {5,10}, {10,11}

and

(15,16,18,20) -> {15,16}, {16,18}, {18,20}

So the overall algorithm may look like this:

• Sort the intervals based on the left endpoint
• Run through intervals until {x,y}, {x',y'} with y < x'
• From beginning to {x,y}, make sorted list of endpoints (no repeats), say a0,a1,...,ak
• Add elementary intervals {ai,a(i+1)} for i = 0...k-1
• Remove intervals up to {x,y} and continue from step 2

Answer 2

You can sort the endpoints and then iterate in order. In order to know whether you are in or out you can keep the number of intervals that cover each point. The left end of the interval contributes +1, while the right contributes -1: (Note that I use TreeMap, which is sorted)

static class Pair<T, K> {
    public Pair(T first, K second){
        this.first = first;
        this.second = second;
    }

    public String toString(){
        return "(" + first + ", " + second + ")";
    }

    T first;
    K second;   
}    

static List<Pair<Integer, Integer>> generateElementaryIntervals(List<Pair<Integer, Integer>> intervals) {
    TreeMap<Integer, Integer> overlaps = new TreeMap<Integer, Integer>();
    for(Pair<Integer, Integer> interval : intervals){
        int value = overlaps.containsKey(interval.first) ? overlaps.get(interval.first)+1 : 1;
        overlaps.put(interval.first, value);

        value = overlaps.containsKey(interval.second) ? overlaps.get(interval.second)-1 : -1;
        overlaps.put(interval.second, value);
    }

    List<Pair<Integer, Integer>>  retValue = new ArrayList<Pair<Integer,Integer>>();

    int overlap = 0;
    boolean in = false;
    int last = 0;
    for(int point : overlaps.keySet()){
        if(in)
            retValue.add(new Pair(last, point));

        overlap += overlaps.get(point);
        last = point;
        in = overlap > 0;
    }

    return retValue;
}    

public static void main(String[] args) {

    List<Pair<Integer, Integer>> l = new ArrayList<Pair<Integer, Integer>>();
    l.add(new Pair<Integer, Integer>(1,5));
    l.add(new Pair<Integer, Integer>(3,10));
    l.add(new Pair<Integer, Integer>(5,11));
    l.add(new Pair<Integer, Integer>(15,18));
    l.add(new Pair<Integer, Integer>(16,20));

    for(Object o : generateElementaryIntervals(l)){
        System.out.println(o.toString());
    }

}