Medium — Array | Sorting | Intervals | Greedy

The Problem

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.

Approach

Sort intervals by start time, then iterate through them maintaining a result list. For each interval, if it overlaps with the last merged interval (current start ≤ last end), merge them by updating the end time to the maximum of both ends, otherwise add it as a new interval.

Time: O(n log n) · Space: O(1)

Code

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        if not intervals:
            return []

        intervals.sort(key=lambda x: x[0])
        result = [intervals[0]]

        for interval in intervals[1:]:
            if interval[0] <= result[-1][1]:
                result[-1][1] = max(result[-1][1], interval[1])
            else:
                result.append(interval)

        return result

Watch It Run

Try it yourself: Open TraceLit and step through every line.

---

Built with TraceLit — the visual algorithm tracer for LeetCode practice.

---

▲ 0 ▼ 0

Comments

Post Comment