Introduction

This pattern describes an efficient technique to deal with overlapping intervals. In a lot of problems involving intervals, we either need to find overlapping intervals or merge intervals if they overlap.

Given two intervals (‘a’ and ‘b’), there will be seven different ways the two intervals can relate to each other:

7. When intervals are equal.

Base case merge

1. sort array
2. get start and end of curr
3. since array is sorted it overlaps if end > curr interval start
4. if it overlaps update end, else assign start and end and add to list
5. don't forget to add start and end after loop

Arrays.sort(intervals, Comparator.comparingInt(ints -> ints[0]));
List<int[]> list = new ArrayList<>();
int[] first = intervals[0];
int start = first[0];
int end = first[1];
for (int i = 1; i < intervals.length; i++) {
    int[] curr = intervals[i];
    if (end >= curr[0]) {
        end = Math.max(end, curr[1]);
    } else {
        list.add(new int[]{start, end});
        start = curr[0];
        end = curr[1];
    }
}
list.add(new int[]{start, end});
return list.toArray(new int[][]{new int[list.size()]});

Insert Intervals

When inserting a new interval in a sorted list:

1. first find the correct index where the new interval can be placed. In other words add all intervals starting before new interval
2. once the correct place is found, we can follow an approach similar to Merge Intervals to insert and/or merge the new interval.
3. add next intervals, merge with new interval if needed

public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> result = new ArrayList<>();

        // add all intervals starting before newInterval
        int i = 0;
        while (i < intervals.length && intervals[i][0] < newInterval[0]) {
            result.add(intervals[i++]);
        }

        // add newInterval
        if (result.isEmpty() || result.get(result.size() - 1)[1] < newInterval[0]) {
            // if there is no overlap, just add the interval
            result.add(newInterval);
        } else {
            // if there is an overlap, merge with the last interval
            var max = Math.max(result.get(result.size() - 1)[1], newInterval[1]);
            result.get(result.size() - 1)[1] = max;
        }

        // add next intervals, merge with newInterval if needed
        while (i < intervals.length) {
            var interval = intervals[i++];
            if (result.get(result.size() - 1)[1] < interval[0]) {
                // if there is no overlap, just add an interval
                result.add(interval);
            } else {
                // if there is an overlap, merge with the last interval
                var max = Math.max(result.get(result.size() - 1)[1], interval[1]);
                result.get(result.size() - 1)[1] = max;
            }
        }
        return result.toArray(new int[result.size()][]);
    }

Intervals Intersection

There are five overlapping possibilities between two intervals ‘a’ and ‘b’. A close observation will tell us that whenever the two intervals overlap, one of the interval’s start time lies within the other interval. This rule can help us identify if any two intervals overlap or not.