# Merge Intervals

Shreya Deep
Last Updated: May 13, 2022

## Introduction

An interval is a set of real numbers lying between any two numbers.

For example, If the starting point of the interval is “a” and the ending point is “b,” then we denote the interval as [a,b]. Two intervals [a,b] and [c,d] are mutually exclusive, if a<=b<c<=d or c<=d<a<=b. So basically, for being mutually exclusive, the two intervals should not have any part of them overlapping with each other.

In this article, we’ll see how to solve the problem-  Merge Intervals frequently asked in Amazon, Microsoft and many product-based companies.

## Problem Statement

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 :

Note: We don’t do anything to the intervals which are not overlapping.

Before directly jumping to the solution, we suggest you try and solve this problem, Merge intervals on Codestudio.

## Approach 1: Brute Force

A simple approach is to first sort the intervals according to their starting point. Then, start from the first interval and compare it with its next interval to check if they are overlapping or not.

If yes, then merge them into one and erase the later interval. Do the same step for each of the other intervals.

We will be erasing here using the vector erase v.erase() function.

The steps are as follows :

### Implementation

Let’s see the implementation of the above approach.

Input

Output

### Complexity Analysis

#### Time Complexity

O(n^2), where n is the number of intervals.

Reason: Since sorting takes O(nlogn) time, and then we’re iterating through the whole interval vector once and erasing some intervals. Now, the time complexity of v.erase() is O(n) and that of traversing the whole vector once is also O(n). So in total, this will be O(n^2). Thus the total time taken is O(nlogn+n^2) ~ O(n^2).

#### Space Complexity

O(N), where N is the number of intervals.

Reason: We’re sorting in place, but the sorting algorithm itself takes O(N) space in the worst case.

## Approach 2: Optimised Approach using another vector.

Another approach with a better time complexity is to first sort the intervals according to their starting point. Once we have sorted, making the comparisons becomes an easy task. Because if the intervals are sorted, and if interval[i] doesn’t overlap with interval[i-1], then interval[i+1] can’t overlap with interval[i-1] because start[i+1]>start[i]>start[i-1].

The steps are as follows :

### Implementation

Let’s see the implementation of the above approach.

Input

Output

### Complexities

#### Time Complexity

O(nlogn), where n is the number of intervals.

Reason: Since sorting takes O(nlogn) time, and then we’re iterating through the whole interval vector once, which takes another O(n) time. Thus the total time taken is O(nlogn+n)~O(nlogn).

#### Space Complexity

O(N), where N is the number of intervals.

Reason: We’re sorting in place, but the sorting algorithm itself takes O(N) space in the worst case. Also we are using another vector of size N for storing answers.
So overall space complexity is O(N)+O(N) = O(2N) asymptotically which is equal to O(N).

If you've made it this far, congratulations, Champ. The problem of "Merge intervals " is now resolved. If you haven't already submitted it to CodeStudio. Without further ado, have it accepted as early as possible.

1. How do you combine intervals?
Answer: Let’s say we have two intervals [a,b] and [c,d] overlapping with each other as a<c<b<d. Then, after merging, the final interval will be [a,d]. So basically, in merging two intervals, we try to find the both extreme points, i.e; th smallest starting point of the two and the largest ending time of the two.

2. What is the best time complexity of the solution for merge intervals?
Answer: The best solution for the merge intervals problem has a complexity of O(nlogn).

3. Where can I submit my “Merge intervals” code?
Answer: You can submit your code on CodeStudio and get it accepted right away.

4. Are there more Data Structures and Algorithms problems in CodeStudio?
Answer: Yes, CodeStudio is a platform that provides both practice coding questions and commonly asked interview questions. The more we’ll practice, the better our chances are of getting into a dream company of ours.

## Key Takeaways

In this article, we discussed the merge intervals problem which is quite similar to the job scheduling problem which involves scheduling jobs such that any two jobs don’t overlap with each other. So you should try solving it.

To practice more such problems, Codestudio is a one-stop destination. This platform will help you acquire effective coding techniques and give you an overview of student interview experience in various product-based companies.

Happy Coding!