PeterQwQ
0%

Leetcode 56 合并区间

发表于

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [start_i, end_i] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

感觉看起来是个板子题。先用暴力写了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        n = len(intervals)
        if n == 1:
            return [intervals[0]]
        intervals.sort(key=lambda x: x[0])
        ans = []
        merged_list = []
        i = 0
        while i < n:
            merged_list = intervals[i]
            for j in range(i+1, n+1):
                if j == n:
                    ans.append(merged_list)
                    return ans
                now_start, now_end = merged_list[0], merged_list[1]
                next_list = intervals[j]
                next_start, next_end = next_list[0], next_list[1]
                if now_end >= next_start and now_end <= next_end:
                    merged_list = [now_start, next_end]
                elif now_end >= next_start and now_end >= next_end:
                    merged_list = [now_start, now_end]
                else:
                    i = j-1
                    ans.append(merged_list)
                    break
            i += 1
        return ans

然后发现题解就是这样写的，我上面写了一坨 if 直接用一个 max 就完事了…
1
2
3
4
5
6
7
8
9
10
class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda x: x[0])
        merged = []
        for interval in intervals:
            if not merged or merged[-1][1] < interval[0]:
                merged.append(interval)
            else:
                merged[-1][1] = max(merged[-1][1], interval[1])
        return merged