56. Merge Intervals¶
Edited by Charles
Medium · Python · Greedy
Problem
Read the original problem on LeetCode.
The official page contains the problem statement, examples, and constraints.
Explanation, examples & other approaches
Core idea
Recall 452. Minimum Number of Arrows to Burst Balloons and 435. Non-overlapping Intervals for the core idea of the following solution. The sorting in the solution is based on the head of each interval, i.e. an ascending order by heads.
Original study notes follow, including intermediate snippets and earlier attempts.
Note:
- Recall 452. Minimum Number of Arrows to Burst Balloons and 435. Non-overlapping Intervals for the core idea of the following solution.
- The sorting in the solution is based on the head of each interval, i.e. an ascending order by heads.
- Attention: the endpoints of the merged intervals are updated by parsing the interval (a list) to an object, which actually share the same address as the merged interval. Thus, any adjustment on the object is also reflected on the interval. The reason why it works is data structures like a list, a dictionary, etc are mutable.
Study record
| Field | Value |
|---|---|
| Attempts | 1 |
| Mastery | ❚ |
| The Latest Attempt | January 30, 2026 |
Python solution¶
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
n = len(intervals)
intervals.sort(key = lambda x: x[0])
result = [intervals[0]]
for i in range(1, n):
cur = intervals[i]
pre = result[-1]
if cur[0] <= pre[1]:
pre[1] = max(pre[1], cur[1])
else:
result.append(cur)
return result