Leecode 435 无重叠区间

在这里插入代码片# 无重叠区间

1、问题描述

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

注意:

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

2、解题思路

显而易见，当区间重叠时，应该舍弃范围大的区间，保留小的区间，这样留下的区间数才会尽可能的多。

1. 首先我们可以对区间进行排序
2. 对排好序的区间判断重叠
   本题中采用的对右端进行排序，那么排序靠后的右端一定不小于前面排序的右端（a[i][1]>=a[j][1], i>j），所以我们此时只通过对于区间左端的判断就可以判定区间是否重叠。 下面的一个区间示意图可以帮助理解：（相当于排序后数组: a[3][2] = { {b, c}, {a, e}, {d, f}}）
   

3、解题代码

void soft(int** a, int left, int right){
     if (left>right) return;int l = left, r = right, key[2];key[0] = a[l][0];key[1] = a[l][1];while (l<r){
    while (l<r && a[r][1]>=key[1]) r--;a[l][0] =a[r][0];a[l][1] =a[r][1];while (l<r && a[l][1]<key[1]) l++;a[r][0] = a[l][0];a[r][1] = a[l][1];}a[l][0] = key[0];a[l][1] = key[1];soft(a, left, l-1);soft(a, l+1, right);
}int eraseOverlapIntervals(int** intervals, int intervalsSize, int* intervalsColSize){
    soft(intervals, 0, intervalsSize-1);int pre=intervals[0][1], t=0;for (int i = 1; i < intervalsSize; i++) {
    if(intervals[i][0]<pre) t++;else pre =intervals[i][1];}return t;
}

452题与此题思路类似，代码为

class Solution {
    
public:static bool cmp(const vector<int>&a, const vector<int>&b) {
    return a[1]<b[1];}int findMinArrowShots(vector<vector<int>>& points) {
    sort(points.begin(), points.end(), cmp);int count=0;int end=points[0][1];for(int i=0; i<points.size(); i++) {
    cout<<points[i][0]<<" "<<points[i][1]<<endl;if(end<points[i][0]){
    end = points[i][1];count++;}}return ++count;}
};