区间问题 LeetCode

爱被打了一巴掌 2023-01-06 11:49 132阅读 0赞

**\*表示重点复习题，没做出来**

## 区间问题 ##

### 1. [56. 合并区间][56.] \* ###

给出一个区间的集合，请合并所有重叠的区间。  
**示例 1:**

输入: intervals = [[1,3],[2,6],[8,10],[15,18]]
    输出: [[1,6],[8,10],[15,18]]
    解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

**示例 2:**

输入: intervals = [[1,4],[4,5]]
    输出: [[1,5]]
    解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

**解法1:** 按区间右端点排序，倒序处理；

class Solution:
        def merge(self, intervals: List[List[int]]) -> List[List[int]]:
            intervals = sorted(intervals, key=lambda x: x[1]) # (x[1], x[0])
            new_inter = []
            intervals_len = len(intervals)
            # 从后往前和并; 从前往后合并 回漏掉一种 后面包括前面所有的情况；
            for i in range(intervals_len-1, 0, -1):
                if intervals[i][0] <= intervals[i-1][1]:
                    intervals[i-1] = [min(intervals[i-1][0], intervals[i][0]), intervals[i][1]]
                else:
                    new_inter.append(intervals[i])
            new_inter.append(intervals[0])  # 少最后一个
            return new_inter

**解法2:** 按区间左端点排序， 这题 左端点排序简单些；

class Solution:
        def merge(self, intervals: List[List[int]]) -> List[List[int]]:
            # 按区间左端点排序； 
            intervals = sorted(intervals, key=lambda x: x[0])
            new_iter = []
            for item in intervals:
                if new_iter and new_iter[-1][1] >= item[0]: # 重合
                    new_iter[-1][1] = max(new_iter[-1][1], item[1])
                else:
                    new_iter.append(item)
                # if not new_iter or new_iter[-1][1] < item[0]: # 不重合，这种也行
                # new_iter.append(item)
                # else:
                # new_iter[-1][1] = max(new_iter[-1][1], item[1])
            return new_iter

## [57. 插入区间][57.] \* ##

给出一个无重叠的 ，按照区间起始端点排序的区间列表。  
在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。  
**示例 1：**

输入：intervals = [[1,3],[6,9]], newInterval = [2,5]
    输出：[[1,5],[6,9]]

**解法1：** 可以理解为和56题一样，合并重叠区间；

class Solution:
        def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
            # 先把 所有数据 加在一起，合并区间；
            intervals.append(newInterval)
            intervals = sorted(intervals, key=lambda x: x[0])
            newiter = []
            for item in intervals:
                if newiter and newiter[-1][1] >= item[0]:  # 合并
                    newiter[-1][1] = max(newiter[-1][1], item[1])
                else:
                    newiter.append(item)
    
            return newiter

## [252. 会议室][252.] ##

给定一个会议时间安排的数组 intervals ，每个会议时间都会包括开始和结束的时间 intervals\[i\] = \[starti, endi\] ，请你判断一个人是否能够参加这里面的全部会议。

**解法1**： 按左端点排序

class Solution:
        def canAttendMeetings(self, intervals: List[List[int]]) -> bool:
            # 出现 两个会议时间重叠，则不能参加 所有会议
            intervals = sorted(intervals, key=lambda x: x[0])
            intervals_len = len(intervals)
            for i in range(1, intervals_len):
                if intervals[i-1][1] > intervals[i][0]:  # 此处 不用等号
                    return False
                    
            return True

## [253. 会议室 II][253. _ II] \* ##

给你一个会议时间安排的数组 intervals ，每个会议时间都会包括开始和结束的时间 intervals\[i\] = \[starti, endi\] ，为避免会议冲突，同时要考虑充分利用会议室资源，请你计算至少需要多少间会议室，才能满足这些会议安排。

**示例 1：**

输入：intervals = [[0,30],[5,10],[15,20]]
    输出：2

**示例2:**

输入：intervals = [[7,10],[2,4]]
    输出：1

**解法1**：

class Solution:
        def minMeetingRooms(self, intervals: List[List[int]]) -> int:
            if not intervals:
                return 0
            # 先按左端点（开始时间）排序，
            intervals = sorted(intervals, key=lambda x:x[0])  
            intervals_len = len(intervals)
            new_iter = [intervals[0][1]]  # 新建数组，存储结束时间
            # room_count = 1
            for i in range(1, intervals_len):
                flag = True
                for j in range(len(new_iter)):
                    if new_iter[j] <= intervals[i][0]:  # 比较结束时间和当前会议开始时间，若存在结束时间<开始时间，则可以复用会议室，更新结束时间
                        new_iter[j] = intervals[i][1] # 更新结束时间
                        flag = False
                        break
                if flag: # 若不存在可以重复利用的会议室，则增加会议室；
                    new_iter.append(intervals[i][1])
                    # room_count += 1
    
            return len(new_iter)  # room_count

## [1272. 删除区间][1272.] ##

实数集合可以表示为若干不相交区间的并集，其中每个区间的形式为 `[a, b)`（左闭右开），表示满足 `a <= x < b` 的所有实数 x 的集合。如果某个区间 `[a, b)` 中包含实数 x ，则称实数 x 在集合中。

给你一个 有序的 不相交区间列表 intervals 和一个要删除的区间 toBeRemoved 。intervals 表示一个实数集合，其中每一项 `intervals[i] = [ai, bi]` 都表示一个区间 `[ai, bi)`。

请你 intervals 中任意区间与 toBeRemoved 有交集的部分都删除。返回删除所有交集区间后， intervals 剩余部分的 有序 列表。换句话说，返回实数集合，并满足集合中的每个实数 x 都在 intervals 中，但不在 toBeRemoved 中。

**示例 1：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIzOTQ0OTE1_size_16_color_FFFFFF_t_70_pic_center]

输入：intervals = [[0,2],[3,4],[5,7]], toBeRemoved = [1,6]
    输出：[[0,1],[6,7]]

**解法1:** 重点就是 怎么 判断两个区间是否相交？ 相交的 怎么拆分！

class Solution:
        def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:
            new_iter = []
            for item in intervals:
                # 完全不相交的情况
                if toBeRemoved[0] > item[1] or toBeRemoved[1] < item[0]:
                    new_iter.append(item)
                    continue
                # 有交集情况 可能切分子集
                left = toBeRemoved[0]  
                right = toBeRemoved[1] 
                if item[0] < left:
                    new_iter.append([item[0], left])
                if right < item[1]:
                    new_iter.append([right, item[1]])
                    
            return new_iter

## [435. 无重叠区间][435.] ##

给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。  
**注意:**

1.  可以认为区间的终点总是大于它的起点。
2.  区间 \[1,2\] 和 \[2,3\] 的边界相互“接触”，但没有相互重叠。

**示例 1:**

输入: [ [1,2], [2,3], [3,4], [1,3] ]
    
    输出: 1
    
    解释: 移除 [1,3] 后，剩下的区间没有重叠。

**解法1：**

class Solution:
        def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
            # 区间的， 按照 右端排序
            if not intervals:
                return 0
            intervals = sorted(intervals, key=lambda x: x[1])
            count = 0
            temp = intervals[0][1]  
            for i in range(1, len(intervals)):  # 不重叠
                if temp <= intervals[i][0]:  
                    temp = intervals[i][1]  # 右端点是 递增的
                else:
                    count += 1  # 需要移除
            return count

## [1288. 删除被覆盖区间][1288.] \* ##

给你一个区间列表，请你删除列表中被其他区间所覆盖的区间。

只有当 `c <= a` 且 `b <= d` 时，我们才认为区间 `[a,b)` 被区间 `[c,d)` 覆盖。

在完成所有删除操作后，请你返回列表中剩余区间的数目。

**示例：**

输入：intervals = [[1,4],[3,6],[2,8]]
    输出：2
    解释：区间 [3,6] 被区间 [2,8] 覆盖，所以它被删除了。

**提示：**

1. 1 <= intervals.length <= 1000
    2. 0 <= intervals[i][0] < intervals[i][1] <= 10^5 对于所有的 i != j：intervals[i] != intervals[j]

**解法1：** 贪心算法

class Solution:
        def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
            # 贪心算法
            # 1. 先按左端点升序排序， 2. 若左端点相同， 则按右端点 降序排列
            intervals = sorted(intervals, key=lambda x: (x[0], -x[1]))
            count = 0
            pre_end = 0  # 品味 这种思路
            for _, end in intervals:
                if end > pre_end:  # 肯定 不会 出现覆盖情况， 不要去统计覆盖了多少区间；
                    count += 1
                    pre_end = end  # 更改end
            return count

## [228. 汇总区间][228.] easy ##

[56.]: https://leetcode-cn.com/problems/merge-intervals/
[57.]: https://leetcode-cn.com/problems/insert-interval/
[252.]: https://leetcode-cn.com/problems/meeting-rooms/
[253. _ II]: https://leetcode-cn.com/problems/meeting-rooms-ii/
[1272.]: https://leetcode-cn.com/problems/remove-interval/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIzOTQ0OTE1_size_16_color_FFFFFF_t_70_pic_center]: /images/20221119/33815b34d4f64f0bb0a10d904693c561.png
[435.]: https://leetcode-cn.com/problems/non-overlapping-intervals/
[1288.]: https://leetcode-cn.com/problems/remove-covered-intervals/
[228.]: https://leetcode-cn.com/problems/summary-ranges/