56. Merge Intervals
Merge Intervals (LeetCode 56) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Greedy Patterns pattern, in the Interval Merging/Scheduling subpattern.
- Blind 75 · #64 of 75 · Intervals
- NeetCode 150 · #131 of 150 · Intervals
- NeetCode 250 · #222 of 250 · Intervals
How to solve Merge Intervals
Merge Intervals is a Interval Merging and Scheduling problem, part of Greedy Patterns. Master interval problems including merge intervals, insert interval, and non-overlapping intervals.
Work towards the solution in these steps:
- Consider sorting the intervals first; how might ordering them help in merging overlapping intervals?
- After sorting, think about iterating through the intervals and comparing the current interval with the last merged interval to decide whether to merge or add a new interval.
- Identify the condition that determines if two intervals overlap and how you can update the merged interval accordingly.
The reference solution runs in O(N log N) time and O(N) space.
The Merge Intervals solution and editorial walks through the full approach with reference code.
Problem statement
Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.
Example 1:
Input: intervals = [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]] Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].
Example 2:
Input: intervals = [[1,4],[4,5]] Output: [[1,5]] Explanation: Intervals [1,4] and [4,5] are considered overlapping.
Constraints:
- 1 <= intervals.length <= 104
- intervals[i].length == 2
- 0 <= starti <= endi <= 104
Topics and companies
Topics: Array, Sorting.
Reported in interviews at Facebook, JPMorgan, Amazon, Bloomberg, Apple, Google, Microsoft, Adobe, Uber, Twitter, eBay, Paypal and others.
How to practise Merge Intervals on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(N log N) time and O(N) space.
Open Merge Intervals in the code editor, or read the Merge Intervals editorial for a worked solution with its approach and complexity analysis.
Where Merge Intervals sits in the DSA pattern sheet
Problems related to Merge Intervals
Other problems that use the same Interval Merging/Scheduling and Greedy Patterns techniques:
- Divide Intervals Into Minimum Number of Groups — Medium, same subpattern
- Insert Interval — Medium, same subpattern
- Meeting Rooms — Easy, same subpattern
- Non-overlapping Intervals — Medium, same subpattern
- Assign Cookies — Easy, same pattern
- Candy — Hard, same pattern
Merge Intervals FAQ
What is the LeetCode number of Merge Intervals?
Merge Intervals is LeetCode problem 56, rated Medium.
What pattern is used to solve Merge Intervals?
Merge Intervals is a Interval Merging and Scheduling problem. It belongs to the Greedy Patterns pattern, in the Interval Merging/Scheduling subpattern.
What is the time complexity of Merge Intervals?
The reference solution runs in O(N log N) time and O(N) space.
Which companies ask Merge Intervals?
Merge Intervals has been reported in interviews at Facebook, JPMorgan, Amazon, Bloomberg, Apple, Google, Microsoft, Adobe, Uber, Twitter, eBay, Paypal and others.