mafeshsho8lmafeshsho8l
Get Started
All coding questions

Merge Intervals

medium
Blind 75NeetCode 150intervalssortingarrays

Problem

Given a list of intervals, merge every set of overlapping intervals and return the resulting non-overlapping intervals covering the same ranges.

Examples

Input: intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
Output: [[1, 6], [8, 10], [15, 18]]
The first two overlap and combine into [1, 6].
Input: intervals = [[1, 4], [4, 5]]
Output: [[1, 5]]
Touching intervals merge.

Constraints

  • • 1 <= intervals.length <= 10^4
  • • Each interval start is at most its end
Hints(tap to reveal)
  • 1. Sort by start time first.
  • 2. Extend the last merged interval when the next one overlaps.
Optimal approach(spoiler)
  1. Sort the intervals by their start value.
  2. Walk through them keeping the most recent merged interval.
  3. If the next interval starts at or before that interval's end, extend its end.
  4. Otherwise push the current interval and start a new one.
  5. O(n log n) time, O(n) output space.

Ready to solve it?

Write your solution in the editor and get an instant AI grade on correctness, edge cases, and complexity.

Practice in the editor