Merge Intervals Explained: Clean Greedy Approach with Python (LeetCode)

Merge Intervals – Problem Overview

The Merge Intervals problem is a classic greedy + sorting problem that frequently appears in coding interviews. Given a list of intervals, the task is to merge all overlapping intervals and return the non-overlapping result.

Key Intuition

The core idea is simple but powerful:

• First, sort all intervals by their start time
• Then, merge intervals only when they overlap with the previous one

Once the intervals are sorted, any overlapping interval must be adjacent. This allows us to solve the problem in a single linear scan after sorting.

Step-by-Step Approach

1. Sort the intervals based on the starting value
2. Initialize the result list with the first interval
3. Iterate through the remaining intervals
4. If the current interval overlaps with the last merged interval, update the end boundary
5. If it does not overlap, start a new interval

Python Implementation

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda x: x[0])
        output = [intervals[0]]

        for start, end in intervals[1:]:
            if start <= output[-1][1]:
                output[-1][1] = max(output[-1][1], end)
            else:
                output.append([start, end])

        return output

Why This Works

Sorting ensures that once an interval does not overlap with the previous one, it cannot overlap with any earlier interval.

This greedy strategy guarantees:

• Time Complexity: O(n log n) due to sorting
• Space Complexity: O(n) for the output list

Edge Cases Covered

• Fully overlapping intervals
• Partially overlapping intervals
• Touching intervals (e.g., [1,4] and [4,5])
• Already non-overlapping intervals

Common Interview Insight

Interviewers are less interested in brute-force merging and more focused on whether you:

• Recognize the need for sorting
• Apply greedy logic correctly
• Reduce the problem to comparing only adjacent intervals

GitHub Repository

You can find the full solution and related interval problems here:

👉 GitHub – LeetCode Interval Problems

Final Thoughts

Merge Intervals is a perfect example of how sorting + greedy thinking can drastically simplify a problem. Once you internalize this pattern, many interval-based problems start to feel intuitive rather than tricky.