• 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

VMWare SDEII Interview

Reversal of LinkedList

Test Cases for Round Function

Binary Tree in Java

Top 10 Interviews Techniqes for Campus Interview in IIT NIT BITS for MTech

Binary Tree Isomorphic to each other

Implement LRU Cache

Hackerearth : Counting Subarrays

There are N nuts and N bolts, u have to find all the pairs of nuts and bolts in minimum no. of iteration

Print vertical sum of all the axis in the given binary tree

Printing intermediate Integers between one element & next element of array

Search element in a matrix with all rows and columns in sorted order

The greedy coins game Dynamic Programming

SAP Off Campus Hiring_ March 2015 Computer Skills

Length of the longest substring without repeating characters

Find Nearest Minimum number in left side in O(n)

BlueStone E-commerce Interview Experience

BFS (Breath First Search)

Maximum of all subarrays of size k

Python Array String

SAP Off Campus Hiring_ March 2015 Sample Questions

Doubly linked list

Find shortest distances between every pair of vertices ( Dynamic Programming Floyd Warshall Algorithm)

SAP Off Campus Hiring_ March 2015 Analytical Aptitude

Find Percentage of Words matching in Two Strings

N Petrol bunks or City arranged in circle. You have Fuel and distance between petrol bunks. Is it possible to find starting point so that we can travel all Petrol Bunks

Naurki.com Security Breach

Best Java Book | Top Java Programming Book for Beginners

Find if two rectangles overlap

Find next greater number with same set of digits

Copyright © 2025 · Genesis Framework · WordPress · Log in