Finding elementary intervals in overlapping intervals

10
votes

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?

3
algorithmdata-structures
What is it that you don't understand? – Kowshik
I understand quite well, but you have not asked a question. There is not question-mark anywhere in your post. Do want a solution in Java? Do you just want an idea how to approach it? Have you already thought about it and are hung up on a specific point? I don't know. – Björn Pollex
Well, hope I've added some direction to the discussion now with a "?" at the end of the description. – Kowshik

3 Answers

8
votes

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
1
votes

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

}
0
votes

A simple algorithm would be to simply read through the entire list of numbers, and create an element for each item in each pair.

Each element would store two values: the number, and whether it is the first or second number (from the input).

Those pairs would then be sorted, first by its internal number, and then by its position (second would go before first)

To print out the list of intervals, you would print each number together with the next number, with the following rules:

  • You wouldn't print repeated numbers (so for example, you wouldn't print 5,5)
  • If you exclusively have a second number, and then a first number, you wouldn't print that elementary interval, since there are no values within that range.