---

前言

整理力扣刷题思路。

• 语言：python
• 题库：来自neetcode: link

---

一、预备知识

---

二、解题思路

1.排序

56.merge-intervals

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

python">class Solution:def merge(self, intervals: List[List[int]]) -> List[List[int]]:intervals.sort()ans = []for inter in intervals:if not ans or ans[-1][1]<inter[0]:ans.append(inter)else:ans[-1][1] = max(ans[-1][1],inter[1])return ans

57.insert-interval

给你一个 无重叠的 ，按照区间起始端点排序的区间列表 intervals，其中 intervals[i] = [starti, endi] 表示第 i 个区间的开始和结束，并且 intervals 按照 starti 升序排列。同样给定一个区间 newInterval = [start, end] 表示另一个区间的开始和结束。

在 intervals 中插入区间 newInterval，使得 intervals 依然按照 starti 升序排列，且区间之间不重叠（如果有必要的话，可以合并区间）。

返回插入之后的 intervals。

注意 你不需要原地修改 intervals。你可以创建一个新数组然后返回它。
link

python">class Solution:def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:intervals.append(newInterval)intervals.sort()ans = []for inter in intervals:if not ans or ans[-1][1]<inter[0]:ans.append(inter)else:ans[-1][1] = max(ans[-1][1],inter[1])return ans

参考56合并区间的做法

435.non-overlapping-intervals

给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。
link

python">class Solution:def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:if len(intervals) < 2:return 0intervals.sort(key = lambda x: x[1])cnt = 0r = intervals[0][1]for i in intervals[1:]:#无重叠，边界移到下一个if r <= i[0]:r = i[1]#有重叠，去掉右边界较大的一个else:cnt += 1r = min(r, i[1])return cnt

1851.minimum-interval-to-include-each-query

给你一个二维整数数组 intervals ，其中 intervals[i] = [lefti, righti] 表示第 i 个区间开始于 lefti 、结束于 righti（包含两侧取值，闭区间）。区间的 长度 定义为区间中包含的整数数目，更正式地表达是 righti - lefti + 1 。

再给你一个整数数组 queries 。第 j 个查询的答案是满足 lefti <= queries[j] <= righti 的 长度最小区间 i 的长度 。如果不存在这样的区间，那么答案是 -1 。

以数组形式返回对应查询的所有答案。
link

python">from heapq import *
class Solution:def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:intervals.sort()ans,minHeap = {},[]i = 0for q in sorted(queries):#左边界不大于q，则q有可能在此区间，所以入堆while i<len(intervals) and intervals[i][0]<=q:heappush(minHeap,[intervals[i][1]-intervals[i][0]+1, intervals[i][1]])i += 1#若右边界小于q，则q不在此区间，弹出while minHeap and minHeap[0][1]<q:heappop(minHeap)ans[q] = minHeap[0][0] if minHeap else -1return [ans[q] for q in queries]

参考neetcode配套视频