# Merge Intervals Problem

## 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.CompareTo(b));
foreach (int[] interval in intervals)
{
if (merged.Count == 0 || merged.Last.Value < interval)
{
}
else
{
merged.Last.Value = Math.Max(merged.Last.Value, interval);
}
}

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.CompareTo(b));
int prev = 0, curr = 1;
while (prev < intervals.Length && curr < intervals.Length)
{
if (intervals[prev] < intervals[curr])
{
prev++;
intervals[prev] = intervals[curr];
curr++;
}
else
{
intervals[prev] = Math.Max(intervals[prev], intervals[curr]);
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.