# Merge Intervals

Posted: 10 Sep, 2020

Difficulty: Moderate

#### You are given N number of intervals, where each interval contains two integers denoting the start time and the end time for the interval.

#### The task is to merge all the overlapping intervals and return the list of merged intervals sorted by increasing order of their start time.

#### Two intervals [A,B] and [C,D] are said to be overlapping with each other if there is at least one integer that is covered by both of them.

#### For example:

```
For the given 5 intervals - [1, 4], [3, 5], [6, 8], [10, 12], [8, 9].
Since intervals [1, 4] and [3, 5] overlap with each other, we will merge them into a single interval as [1, 5].
Similarly, [6, 8] and [8, 9] overlap, merge them into [6,9].
Interval [10, 12] does not overlap with any interval.
Final List after merging overlapping intervals: [1, 5], [6, 9], [10, 12].
```

##### Input Format:

```
The first line of input contains an integer N, the number of intervals.
The second line of input contains N integers, i.e. all the start times of the N intervals.
The third line of input contains N integers, i.e. all the end times of the N intervals.
```

##### Output Format:

```
Print S lines, each contains two single space-separated integers A, and B, where S is the size of the merged array of intervals, 'A' is the start time of an interval and 'B' is the end time of the same interval.
```

#### Note

```
You do not need to print anything, it has already been taken care of. Just implement the given function.
```

##### Constraints:

```
1 <= N <= 10^5
0 <= START, FINISH <= 10^9
Time Limit: 1sec
```

SIMILAR PROBLEMS

City Lights

Posted: 9 Jul, 2022

Difficulty: Hard

Best time to buy and sell stock

Posted: 2 Sep, 2022

Difficulty: Moderate

Best time to buy and sell stock II

Posted: 5 Sep, 2022

Difficulty: Moderate

Array Rotation

Posted: 21 Oct, 2022

Difficulty: Easy

Find The Single Element

Posted: 30 Oct, 2022

Difficulty: Easy