💬 Discord
Sign In
NeetCode #833LC-56MediumIntervalsBlind 75NC 150NC 250
← Back to All Problems

#833 · #56 · Merge Intervals(合并区间)

📌 Problem Statement & Constraints

You are given an array of intervals intervals. Merge all overlapping intervals and return the non-overlapping intervals that cover the same union. Two intervals overlap when one starts at or before the other ends. Constraints: 1 <= intervals.length <= 10^4, 0 <= intervals[i][0] <= intervals[i][1] <= 10^4.

💡 Core Algorithmic Approaches

  1. Sort by start so that overlapping intervals become adjacent.
  2. Scan left to right, appending a new interval only when the current one starts after the last merged interval ends.
  3. Otherwise extend the last merged interval's end to max(end, currentEnd) -- the max matters because an interval can be fully contained.
  4. Sorting by start guarantees that no later interval can overlap an earlier one without also overlapping the current merged block.

💻 Benchmark Python3 Implementation

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda x: x[0])
        res = []
        for s, e in intervals:
            if res and s <= res[-1][1]:
                res[-1][1] = max(res[-1][1], e)   # contained intervals keep the max end
            else:
                res.append([s, e])
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n log n): the sort dominates the linear merge.
💾 Space Complexity
O(n) for the output.

⚠️ Interview Pitfalls & Follow-ups

  • Using res[-1][1] = e without the max: a nested interval like [1,10] followed by [2,3] would shrink the merged end to 3.
  • Sorting by end instead of start: with this merge strategy the ordering must be by start, otherwise a later interval can start before the running end.
  • Treating touching intervals as disjoint: [1,2] and [2,3] share the point 2 and must merge, so the test is s <= res[-1][1].
  • Modifying the input in place: mutating res[-1] is fine because those are fresh lists, but mutating the input tuples would be a bug.