Algorithm to find intersection of intervals

Question

I have two lists, each of sets of intervals. I want to find the intersection of the two lists.

Eg.
List1 = [{1, 10}, {15, 25}, {30, 32}];
List2 = [{3,5}, {9,14}, {17,20}];

Result:

IntersectionList = [{3,5}, {9,10}, {17,20}];

I've tried using: Java algorithm for find intersection between intervals but this just has one object in the first list.

I'd like to be able to give multiple interval objects in each list.

public class CalendarTimeSlot {
    private long from;
    private long to;
}

public class IntersectIntervalsHelper {

        public static void main(String[] args) {

        List<CalendarTimeSlot> l1 = new ArrayList<>();
        l1.add(new CalendarTimeSlot(1, 10));
        l1.add(new CalendarTimeSlot(15, 25));
        l1.add(new CalendarTimeSlot(30, 32));

        List<CalendarTimeSlot> l2 = new ArrayList<>();
        l2.add(new CalendarTimeSlot(3, 5));
        l2.add(new CalendarTimeSlot(9, 14));
        l2.add(new CalendarTimeSlot(17, 20));

        //todo code here to do l1 intersection l2 slots
    }

}

Sample Input:

List1 = [{1, 10}, {15, 25}, {30, 32}];
List2 = [{3,5}, {9,14}, {17,20}];

Result:

IntersectionList = [{3,5}, {9,10}, {17,20}];

What should be the result of the second interval in case it's `{9,20}`? It could be either `{9,10}` or `{15,20}` — Robert Kock, Jun 24 '19 at 08:06
It has to be both. The o/p should contain: [{3,5}, {9,10}, {15,20}]; — Shivang Tripathi, Jun 24 '19 at 08:12
Why does Expected Output show 2 lists? Is it input which you have wrongly labelled? — Gaurav Singh, Jun 24 '19 at 08:12
You could represent the intervals by a BitSet where each bit index is the natural number and true/false means whether it belongs to the interval or not. Then use the BitSet.And method to find the intersection. After this, just somehow dump the result back into the List of subintervals. — Mário Uhrík, Jun 24 '19 at 08:13
Hint: you only dropped requirements so far. If you want to receive more positive feedback ... consider *trying something* yourself. Don't expect that *others* should do the work for you. — GhostCat, Jun 24 '19 at 08:18
Loop over the first list and within that, loop over the 2nd list. For each pair of elements, check whether there's an overlap and add it to the result if so. — Robert Kock, Jun 24 '19 at 12:13
@RobertKock: this results in an O(N²) process. Very inefficient. — , Jun 24 '19 at 12:23

score 2 · Answer 1 · answered Jun 24 '19 at 08:46

Flatten both lists by ignoring the pairs and make sure they are sorted. You get two lists of numbers such that every interval is comprised between even and odd indexes (starting from zero).

Now consider a standard merging process that will generate a third list.

1, 10, 15, 25, 30, 32
3, 5, 9, 14, 17, 20

gives

1, 3, 5, 9, 10, 14, 15, 17, 20, 25, 30, 32

At the same time, you can annotate the list to indicate if you are inside or outside of either list

  1, 3, 5, 9, 10, 14, 15, 17, 20, 25, 30, 32
oo io ii io ii  oi  oo  io  ii  io  oo  io  oo

The desired output is made of the ii intervals,

  3, 5, 9, 10, 17, 20
   ii    ii      ii

Wouldn't work if the 2nd element of the 2nd list is `{4,14}` instead of `{9,14}` — Robert Kock, Jun 24 '19 at 12:18
@RobertKock: overlaps are not allowed. If you allow them, we can replace inside/outside by an "insideness level". — , Jun 24 '19 at 12:24

score 0 · Answer 2 · answered Jun 24 '19 at 08:38

Make a single list containing pairs with all interval ends.
Every pair is (value; +1/-1 for interval start/end)
Sort this list by value.
Make ActiveCount=0.
Run through the sorted list, incrementing ActiveCount with start/end flag.
When ActiveCount becomes 2, output interval begins.
When ActiveCount becomes 1 (after 2!), output interval ends.

score 0 · Answer 3 · answered Jun 24 '19 at 08:40

public static List<CalendarTimeSlot> createIntersection(List<CalendarTimeSlot> l1, List<CalendarTimeSlot> l2) {
    List<CalendarTimeSlot> intersectedSlots = new ArrayList<>();
    int length1 = l1.size();
    int length2 = l2.size();
    int l1Counter = 0, l2Counter = 0;
    while (l1Counter<length1 && l2Counter<length2) {
        CalendarTimeSlot calendarTimeSlot1 = l1.get(l1Counter);
        CalendarTimeSlot calendarTimeSlot2 = l2.get(l2Counter);

        long from = 0, to =0;
        if(calendarTimeSlot1.getFrom()<=calendarTimeSlot2.getFrom()) {
            from = calendarTimeSlot2.getFrom();

            //smaller on is the "to"
            if(calendarTimeSlot1.getTo()>=calendarTimeSlot2.getTo()) {
                to = calendarTimeSlot2.getTo();
            } else {
                to = calendarTimeSlot1.getTo();
            }
        } else {
            //l1's from is greater
            if(calendarTimeSlot2.getTo()>calendarTimeSlot1.getFrom()) {
                from = calendarTimeSlot1.getFrom();

                //smaller on is the "to"
                if(calendarTimeSlot1.getTo()>=calendarTimeSlot2.getTo()) {
                    to = calendarTimeSlot2.getTo();
                } else {
                    to = calendarTimeSlot1.getTo();
                }
            }
        }

        if(calendarTimeSlot1.getTo()<calendarTimeSlot2.getTo()) {
            l1Counter++;
        } else {
            l2Counter++;
        }

        if(from>0 && to>0) {
            intersectedSlots.add(new CalendarTimeSlot(from, to));
        }

    }

    return intersectedSlots;
}

Algorithm to find intersection of intervals

3 Answers3