# 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[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

*because of the*

**O(n)**`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

*because we have to create new array with size*

**O(n)**`prev + 1`

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

.