• Skip to primary navigation
  • Skip to content
  • Skip to primary sidebar
  • Skip to secondary sidebar

GoHired

Interview Questions asked in Google, Microsoft, Amazon

Join WeekEnd Online Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

  • Home
  • Best Java Books
  • Algorithm
  • Internship
  • Certificates
  • About Us
  • Contact Us
  • Privacy Policy
  • Array
  • Stack
  • Queue
  • LinkedList
  • DP
  • Strings
  • Tree
  • Mathametical
  • Puzzles
  • Graph

Leetcode: Merge Intervals

January 18, 2020 by Arshdeep Singh

Given a collection of intervals, merge all overlapping intervals.

Example 1:
Input: [[2,6],[8,10],[15,18], [1,3]]
Output: [ [1,6] , [8,10] , [15,18] ]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

Example
Solution 1st and 2nd interval combined


Example 2:
Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

Question Link: Merge Intervals

Solution: 

The brute force way to approach such a problem is select each interval and check from all the rests if it they can be combined?
If Yes, combine them, form the new interval and check again.
If No, put that interval in the result and continue.

But the above solution, have some problems:
1. It is actually difficult to implement.
2. It requires multiple recursions and graphs (read Connected Components).
3. This is not optimal [ O(N^2) Time Complexity ].

In conclusion, its better to further think about it.

Lets say if the intervals come in a partilar order, say sorted on the basis of first and then second values. Therefore, we know for each interval it can only combine with interval following it or previous to it and if possible we can combine intervals in a linear fashion.

Explaination

Firstly sort all the intervals based on firstly the left and then right pair values.

For each interval inteval[i] (a,b), select l and r as left and right hand of the interval:
Check if inteval[i+1] is can be combined to inteval[i].
If Yes, make r = max(r, interval[i+1].right) and continue with the current interval.
If No, save the current interval and continue to the next interval.

Now lets try to solve on the following example:
[[12,15], [12,17], [2,4], [16,18], [4,7], [9,11], [1,2]]

First step is to sort the intervals. After sorting we get:
[[1,2], [2,4], [4,7], [9,11], [12,15], [12,17], [16,18]]

Then:

Initial Intervals
l=1 and r=3
l=1 and r=4
l=1 and r=7
Save the previous interval and new: l=9 and r=11
Save the previous interval and new: l=12 and r=15
l=12 and r=17
l=12 and r=18
Save the previous interval and we get the final answer.

Code

Implemented in C++.
First we need to write a comparator to help sort intervals in vectors format. We wouldn’t require this if the intevals were given in pairs format.

static bool comp(const vector<int> a,const vector<int> b){
    if(a[0]==b[0]) return a[1]<b[1];
    else return a[0]<b[0];
}

Main code to implement the logic:

vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if(intervals.size()==0) return intervals; // if zero size
        sort(intervals.begin(), intervals.end(), comp); //sorting using custom comparator
        vector<vector<int>> ans; //for saving result
        int l=0,r=INT_MIN; // initial parameters
        for(int i=0;i<intervals.size();i++){
            if(intervals[i][0]<=r){ // if intervals can be merged
                r = max(r, intervals[i][1]);
            }
            else{ // if intervals can't be merged
                if(i>0)ans.push_back(vector<int>{l,r}); //saving the result
                l=intervals[i][0]; r=intervals[i][1];
            }
        }
        ans.push_back(vector<int>{l,r});
        return ans;
    }

The time complexity of this solution will be:
1. Sort the intervals: O( N logN ).
2. Merge Logic is based on Two pointer technique. Each interval is selected only once: so O( N ).

The final time complexity will be O( N logN ).

Similar Articles

Filed Under: Amazon Interview Question, Flipkart Interview Questions, Google, Interview Questions, LeetCode Tagged With: Array, LeetCode, MergeIntervals

Reader Interactions

Primary Sidebar

Join WeekEnd Online/Offline Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

Join WeekEnd Online/Offline Batch from 4-April-2020

WhatsApp us

Secondary Sidebar

Custom Search

  • How I cracked AMAZON
  • LeetCode
  • Adobe
  • Amazon
  • Facebook
  • Microsoft
  • Hacker Earth
  • CSE Interview

Top Rated Questions

Binary Tree in Java

DFS (Depth First Search)

How strtok() Works

Apriori algorithm C Code Data Mining

Find loop in Singly linked list

robot standing at first cell of an M*N matrix. It can move only in two directions, right and down. In how many ways, it can reach to the last cell i.e. (M, N) Code it

Amazon Interview Experience – SDE Chennai

Trapping Rain Water

Skiing on Mountains Matrix

Fibonacci Hashing & Fastest Hashtable

TicTacToe Game As Asked in Flipkart

K’th Largest Element in BST when modification to BST is not allowed

25 horses 5 tracks Find 3 fastest puzzle

‘N’ Story Building, with 1,2,3 steps how many ways can a person reach top of building.

Add Sub Multiply very large number stored as string

Edit Distance ( Dynamic Programming )

Count number of ways to reach a given score in a game

Closed Parentheses checker

Practo Hiring Experience

Test Cases for Round Function

CodeChef Code SGARDEN

Find and print longest consecutive number sequence in a given sequence in O(n)

Find if a binary tree is height balanced ?

Minimum insertions to form a palindrome

Coin Collection Dynamic Programming

Knight Tour Problem (Graph – Breadth First Search)

Reversal of LinkedList

Length of the longest substring without repeating characters

Find min element in Sorted Rotated Array (Without Duplicates)

Mirror of Tree

Copyright © 2025 · Genesis Framework · WordPress · Log in