- 一、题目描述
- 二、解题思路
- 1. 思路
- 2. 步骤
- 3. 图形解说
- 三、我的题解
一、题目描述
给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。
示例 1: 输入: intervals = [[1,2],[2,3],[3,4],[1,3]] 输出: 1 解释: 移除 [1,3] 后，剩下的区间没有重叠。 示例 2: 输入: intervals = [ [1,2], [1,2], [1,2] ] 输出: 2 解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。 示例 3: 输入: intervals = [ [1,2], [2,3] ] 输出: 0 解释: 你不需要移除任何区间，因为它们已经是无重叠的了。
提示:
1 <= intervals.length <= 105 intervals[i].length == 2 -5 * 104 <= starti < endi <= 5 * 104
二、解题思路 1. 思路
该题也就是求最多不重叠的区间数，我们很容易想到贪心算法。
我们现在想一个数轴，数轴上有很多区间，我们要找出不重叠区间的最大数，那么我们可以从左到右遍历区间上的数轴，为了给后面的区间留下尽可能多的位置：
- 我们先选取一个右端点最小的区间 inter0，然后丢弃与该区间重叠的区间，直到遇到下一个不与 inter0 重叠的区间 inter1 ；
- 然后又以区间 inter1 为基准，丢弃与该区间重叠的区间，直到遇上下一个不重叠的区间…
- 重复以上步骤
该题中的贪心体现在，为了给后面的区间留下尽可能多的位置，我们选取右端点尽可能小的区间。
2. 步骤- 为了将区间放在数轴上，同时我们又要尽量选取右端点尽可能小的区间：我们需要对所有区间 按照右端点进行排序。
- 然后我们选取右端点最小的，开始向后遍历。
总结：按照右边界排序，就要从左向右遍历，因为右边界越小越好，只要右边界越小，留给下一个区间的空间就越大，所以从左向右遍历，优先选右边界小的。
做法：按照右边界排序，从左向右记录非交叉区间的个数。最后用区间总数减去非交叉区间的个数就是需要移除的区间个数了。
思想：右边界排序之后，局部最优：优先选右边界小的区间，所以从左向右遍历，留给下一个区间的空间大一些，从而尽量避免交叉。全局最优：选取最多的非交叉区间。局部最优推出全局最优，试试贪心！
3. 图形解说这里记录非交叉区间的个数还是有技巧的，如图：
区间 1，2，3，4，5，6 都按照右边界排好序，如上图。
每次取非交叉区间的时候，都是用右边界最小的来做分割点（这样留给下一个区间的空间就越大），所以第一条分割线就是区间1结束的位置。
接下来就是找大于区间1结束位置的区间，是从区间4开始。那有同学问了为什么不从区间5开始？别忘已经是按照右边界排序的了。
区间4结束之后，在找到区间6，所以一共记录非交叉区间的个数是三个。
总共区间个数为6，减去非交叉区间的个数3。移除区间的最小数量就是3。
参考代码随想录：435. 无重叠区间
三、我的题解
按照上述解题思路，我给出了 Go 语言题解：
func eraseOverlapIntervals(intervals [][]int) int {
if len(intervals) == 0{
return 0
}
//按照区间右端从小到大排序
sort.Slice(intervals, func(i,j int) bool {return intervals[i][1] < intervals[j][1]})
now := intervals[0]
n := 1
for i:=1;i
if intervals[i][0] >= now[1]{
now = intervals[i]
n++
}
}
return len(intervals) - n
}
评判结果：
