Merge Intervals Problem

Tagged: Sorting, Array, Two Pointers, Linked List

Problem#

Given a two dimensional array intervals where every element intervals[i] = [starti, endi], our task is to merge all overlapping intervals and return an array of non-overlapping intervals that cover all the intervals in the input.

Below are some of the examples:

Input: [[2,4],[8,10],[1,5],[0,7]]
Output: [[0,7],[8,10]]
Explanation: [0,7] covers [1,5] and [2,4].

Input: [[1,3],[2,6]]
Output: [[1,6]]
Explanation: [1,3] and [2,6] overlap so it is merged into [1,6].

Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: [1,4] and [4,5] are considered to overlap so it is merged into [1,5].

This tutorial will show you some algorithms that can be used to solve this problem.

Solution#

In the first case above where [0,7] covers [1,5] and [2,4], the position of the start of [1,5] and [2,4] which are 1 and 2 appear not in ascending order ([2,4] appears earlier than [1,5]). Therefore, we must sort the intervals first so that they will appear as contiguous intervals then the merging process would start by comparing previous end and current start.

Sorting and Doubly Linked List#

After we sort the intervals, then we start merging the contiguous intervals by utilizing Doubly Linked List where the AddLast operation has O(1) complexity.

public int[][] Merge(int[][] intervals)
{
    Array.Sort(intervals, (a, b) => a[0].CompareTo(b[0]));
    LinkedList<int[]> merged = new LinkedList<int[]>();
    foreach (int[] interval in intervals)
    {
        if (merged.Count == 0 || merged.Last.Value[1] < interval[0])
        {
            merged.AddLast(interval);
        }
        else
        {
            merged.Last.Value[1] = Math.Max(merged.Last.Value[1], interval[1]);
        }
    }

    return merged.ToArray();
}

Time Complexity O(n log n) and Space Complexity O(n) because of the merged linked list.

Sorting and Two Pointers#

Similar to previous approach, but this time we use Two Pointers to merge the contiguous intervals.

public int[][] MergeUsingTwoPointers(int[][] intervals)
{
    Array.Sort(intervals, (a, b) => a[0].CompareTo(b[0]));
    int prev = 0, curr = 1;
    while (prev < intervals.Length && curr < intervals.Length)
    {
        if (intervals[prev][1] < intervals[curr][0])
        {
            prev++;
            intervals[prev] = intervals[curr];
            curr++;
        }
        else
        {
            intervals[prev][1] = Math.Max(intervals[prev][1], intervals[curr][1]);
            curr++;
        }
    }

    return intervals.Take(prev + 1).ToArray();
}

Time Complexity O(n log n) and Space Complexity O(n) because we have to create new array with size prev + 1.

Please note that whether we use array copy or other method, it basically creates new array with size prev + 1.