• 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

The Magic HackerEarth Nirvana solutions Hiring Challenge

Memory Efficient LinkedList

SAP Off Campus Hiring_ March 2015 Computer Skills

ADOBE Aptitude C Language Test

Longest Increasing Subsequence

Number of Islands BFS/DFS

LeetCode: Binary Tree Maximum Path Sum

Find two non repeating elements in an array of repeating elements

Apriori algorithm C Code Data Mining

Generic Object Oriented Stack with Template

Adobe Interview Questions 8 month Exp

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

Python Dictionaries

Given array of 0’s and 1’s. All 0’s are coming first followed by 1’s. find the position of first 1

C++ OOPs Part2

Find min element in Sorted Rotated Array (Without Duplicates)

Possible sizes of bus to carry n groups of friends

Print Power Set of a Set

write a c program that given a set a of n numbers and another number x determines whether or not there exist two elements in s whose sum is exactly x

Add Sub Multiply very large number stored as string

Diagonal Traversal of Binary Tree

FizzBuzz Solution C C++

Level order traversal in Spiral form

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

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

The greedy coins game Dynamic Programming

Regular Expression Matching

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

Find the kth number with prime factors 3, 5 and 7

Introduction To Number Theory ( Part 1 )

Copyright © 2025 · Genesis Framework · WordPress · Log in