区间问题

站长

2024年06月07日 20:38 · 阅读数 31

区间问题

本文是面试经典 150 题区间问题的详细解读。

LeetCode中的区间问题通常涉及到对一个或多个区间进行操作，如合并区间、查找区间交集、找到覆盖指定点的区间等等。以下是一些常见的LeetCode区间问题：

合并区间：给定一组区间，将重叠的区间合并成一个区间。
区间交集：给定两个区间，找到它们的交集。
插入区间：给定一个有序的区间列表和一个新的区间，将新区间插入到列表中并合并任何重叠的区间。
找到覆盖指定点的区间：给定一组区间和一个点，找到包含该点的区间。
最大重叠区间数：给定一组区间，找到最大重叠区间数。
区间树：实现一个区间树，以支持区间查找、插入和删除等操作。

以上仅是一些常见的区间问题，LeetCode上还有许多其他类型的区间问题需要解决。要解决这些问题，通常需要使用一些技巧，如排序、扫描线算法、线段树、分治等等。

228. 汇总区间 - 力扣（Leetcode）

给定一个 无重复元素 的有序整数数组 nums 。

返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表。也就是说，nums 的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个范围但不属于 nums 的数字 x 。

列表中的每个区间范围 [a,b] 应该按如下格式输出：

"a->b" ，如果 a != b
"a" ，如果 a == b

示例 1：

输入： nums = [0,1,2,4,5,7]
输出： ["0->2","4->5","7"]
解释： 区间范围是：
[0,2] --> "0->2"
[4,5] --> "4->5"
[7,7] --> "7"

示例 2：

输入： nums = [0,2,3,4,6,8,9]
输出： ["0","2->4","6","8->9"]
解释： 区间范围是：
[0,0] --> "0"
[2,4] --> "2->4"
[6,6] --> "6"
[8,9] --> "8->9"

提示：

0 <= nums.length <= 20
-231 <= nums[i] <= 231 - 1
nums 中的所有值都 互不相同
nums 按升序排列

这个题很简单，注意写对循环条件即可。

class Solution:
    def summaryRanges(self, nums: List[int]) -> List[str]:
        l,r = 0,0
        res = []
        while r < len(nums):
            while r+1 < len(nums) and nums[r+1] == nums[r] + 1: 
                r += 1
            if l == r:
                res.append(str(nums[l]))
            else:
                res.append(f'{nums[l]}->{nums[r]}')
            l = r = r + 1
            
        return res

主要思路是使用双指针，左指针 l 指向区间的起点，右指针 r 指向区间的终点。在遍历整个数组的过程中，当 nums[r+1] - nums[r] != 1 时，说明当前的区间已经不连续了，需要将当前的区间保存下来。

具体步骤如下：

定义两个指针 l 和 r，分别指向区间的起点和终点。
遍历整个数组 nums，当 nums[r+1] - nums[r] != 1 时，说明当前的区间已经不连续了，需要将当前的区间保存下来。
将保存下来的区间转换成题目要求的格式 "start->end"，并将其添加到结果列表中。
将左右指针都移动到下一个区间的起点。
遍历完成后，需要再次检查是否还有未保存的区间，如果有，同样需要将其保存并添加到结果列表中。

最后返回结果列表即可。

该函数的时间复杂度为 O(n)O(n)O(n)，其中 nnn 是数组的长度，需要遍历整个数组一次；空间复杂度为 O(1)O(1)O(1)，除了返回值以外，空间复杂度是常数级别的。

总体来说，这是一段比较简洁清晰的代码实现，也是一种比较常见的解题思路。

56. 合并区间 - 力扣（Leetcode）

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

示例 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 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 104

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

        intervals.sort()
        # intervals.sort(key = lambda i:i[0])

        merge = []

        for i in intervals:
            if not merge or merge[-1][1]<i[0]:
                # merge为空或者merge最后一项的区间和当前区间不重合，直接将当前区间加入merge
                merge.append(i)
            else:
                merge[-1][1] = max(merge[-1][1],i[1])
        
        return merge

intervals.sort()：对区间列表 intervals 进行排序，排序的关键字是区间左端点 i[0]，这一步保证了区间的左端点是单调递增的。
merge = []：初始化合并后的区间列表为空。
for i in intervals:：遍历每一个区间。
if not merge or merge[-1][1] < i[0]:：如果 merge 列表为空，或者 merge 列表中的最后一个区间的右端点小于当前区间的左端点，则将当前区间加入 merge 列表。
else:：如果 merge 列表中的最后一个区间的右端点大于等于当前区间的左端点，则需要将当前区间与 merge 列表中的最后一个区间进行合并。
merge[-1][1] = max(merge[-1][1], i[1])：将 merge 列表中的最后一个区间的右端点更新为当前区间和最后一个区间的右端点的最大值。
return merge：返回合并后的区间列表 merge。

该算法的时间复杂度为 O(nlog⁡n)O(n\log n)O(nlogn)，其中 nnn 为区间的个数。排序的时间复杂度为 O(nlog⁡n)O(n\log n)O(nlogn)，遍历区间的时间复杂度为 O(n)O(n)O(n)，因此总时间复杂度为 O(nlog⁡n)O(n\log n)O(nlogn)。

57. 插入区间 - 力扣（Leetcode）

给你一个 无重叠的 ，按照区间起始端点排序的区间列表。

在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。

示例 1：

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

示例 2：

输入： intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出： [[1,2],[3,10],[12,16]]
解释： 这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。

提示：

0 <= intervals.length <= 104
intervals[i].length == 2
0 <= intervals[i][0] <= intervals[i][1] <= 105
intervals 根据 intervals[i][0] 按升序排列
newInterval.length == 2
0 <= newInterval[0] <= newInterval[1] <= 105

这个题你说他简单，它就是非常简单，只需要在上一题的代码上加上一行代码即可。

就是把那个newInterval加到Intervals里边，题目就又变成了合并区间问题，也省去了比来比去的麻烦。

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        intervals.append(newInterval) # 就加了这一行
        intervals.sort()
        merge = []
        for i in intervals:
            if not merge or merge[-1][1]<i[0]:
                merge.append(i)
            else:
                merge[-1][1] = max(merge[-1][1],i[1])
        return merge

intervals.append(newInterval)：将待插入的新区间 newInterval 加入到原始区间列表 intervals 中。
intervals.sort()：对区间列表 intervals 进行排序，排序的关键字是区间左端点 i[0]，这一步保证了区间的左端点是单调递增的。
merge = []：初始化合并后的区间列表为空。
for i in intervals:：遍历每一个区间。
if not merge or merge[-1][1] < i[0]:：如果 merge 列表为空，或者 merge 列表中的最后一个区间的右端点小于当前区间的左端点，则将当前区间加入 merge 列表。
else:：如果 merge 列表中的最后一个区间的右端点大于等于当前区间的左端点，则需要将当前区间与 merge 列表中的最后一个区间进行合并。
merge[-1][1] = max(merge[-1][1], i[1])：将 merge 列表中的最后一个区间的右端点更新为当前区间和最后一个区间的右端点的最大值。
return merge：返回合并后的区间列表 merge。

452. 用最少数量的箭引爆气球 - 力扣（Leetcode）

There are some spherical balloons taped onto a flat wall that represents the XY-plane. The balloons are represented as a 2D integer array points where points[i] = [xstart, xend] denotes a balloon whose horizontal diameter stretches between xstart and xend. You do not know the exact y-coordinates of the balloons.

Arrows can be shot up directly vertically (in the positive y-direction) from different points along the x-axis. A balloon with xstart and xend is burst by an arrow shot at x if xstart <= x <= xend. There is no limit to the number of arrows that can be shot. A shot arrow keeps traveling up infinitely, bursting any balloons in its path.

Given the array points, return the minimum number of arrows that must be shot to burst all balloons.

Example 1:

Input: points = [[10,16],[2,8],[1,6],[7,12]]
Output: 2
Explanation: The balloons can be burst by 2 arrows:
- Shoot an arrow at x = 6, bursting the balloons [2,8] and [1,6].
- Shoot an arrow at x = 11, bursting the balloons [10,16] and [7,12].

Example 2:

Input: points = [[1,2],[3,4],[5,6],[7,8]]
Output: 4
Explanation: One arrow needs to be shot for each balloon for a total of 4 arrows.

Example 3:

Input: points = [[1,2],[2,3],[3,4],[4,5]]
Output: 2
Explanation: The balloons can be burst by 2 arrows:
- Shoot an arrow at x = 2, bursting the balloons [1,2] and [2,3].
- Shoot an arrow at x = 4, bursting the balloons [3,4] and [4,5].

Constraints:

1 <= points.length <= 105
points[i].length == 2
-231 <= xstart < xend <= 231 - 1

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        points.sort(key=lambda x:x[1])
        count = 1

        end = points[0][1]
        
        for p in points:
            if end < p[0]:
                end = p[1]
                count +=1
        
        return count

points.sort(key=lambda x:x[1])：对气球列表 points 进行排序，排序的关键字是气球的右边界 x[1]，将右边界小的气球排在前面。
count = 1：初始化引爆的箭的数量为 1，因为至少需要一支箭来引爆第一个气球。
end = points[0][1]：初始化变量 end 为第一个气球的右边界，即当前箭可以引爆的最远位置。
for p in points:：遍历气球列表中的每一个气球。
if end < p[0]:：如果当前箭的最远位置 end 小于当前气球的左边界 p[0]，说明当前箭不能引爆当前气球，需要使用一支新的箭，箭的数量加 1，同时更新箭的最远位置 end 为当前气球的右边界 p[1]。
return count：返回最少需要引爆的箭的数量。

这个算法的时间复杂度是 O(nlog⁡n)O(n\log n)O(nlogn)，其中 nnn 是气球的数量。排序需要 O(nlog⁡n)O(n\log n)O(nlogn) 的时间，遍历气球需要 O(n)O(n)O(n) 的时间，因此总时间复杂度是 O(nlog⁡n)O(n\log n)O(nlogn)。

转载自:https://juejin.cn/post/7223343320298504253