贪心

区间覆盖

套路比较固定

45. 跳跃游戏 II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int jump(vector<int>& nums) {
    int len = nums.size();
    int cnt = 0;
    int right = 0;
    int next = 0;
    int i = 0;
    while(next < len-1){                //终止条件: 右边界能跳出整个数组了
        right = next;
        for( ;i <= right;i++){          //[left,right]区间中
            next = max(next,i+nums[i]); //更新数据
        }
        cnt++;							//记录更新的数据
    }
    return cnt;
}

763. 划分字母区间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector<int> partitionLabels(string s) {
    vector<int>last(26,0);
    int len = s.length();
    for(int i = 0;i < len;i++){
        last[s[i]-'a']=i;
    }
    vector<int>results;
    int i = 0;
    int left = 0,right = 0;
    while(right < len-1){					//终止条件: 右边界能跳出整个数组了
        left = i;
        right = last[s[i]-'a'];
        for(;i <= right;i++){				//[left, right]
            if(last[s[i]-'a'] > right){
                right = last[s[i] - 'a'];	//更新数据
            }
        }
        results.push_back(right-left+1);	//记录更新的数据
    }
    return results;
}

区间选点

主要考虑一个贪心思想
对于排好序的一个气球，如果后面的气球和此气球有重叠直接戳爆即可

452. 用最少数量的箭引爆气球

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
static bool cmp(vector<int>a,vector<int>b){
    return a[1]<b[1];
}
int findMinArrowShots(vector<vector<int>>& points) {
    sort(points.begin(),points.end(),cmp);
    int len = points.size();
    int cnt = 0;
    for(int i=0;i<len;) {
        int right = points[i][1];
        while(i<len&&points[i][0]<=right){  //当前区间的[left, right]
            i++;							//戳爆此气球
        }
        cnt++;                              //记录更新的数据
    }
    return cnt;
}

区间不相交选择

435. 无重叠区间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
static bool cmp(vector<int>&a, vector<int>&b){
    return a[1] < b[1];
}
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
    sort(intervals.begin(),intervals.end(),cmp);
    int len = intervals.size();
    int cnt=0;
    int prev = INT_MIN;
    for(int i = 0;i < len;i++){
        if(intervals[i][0] < prev){
            cnt++;
        }else{
            prev = intervals[i][1];
        }
    }
    return cnt;
}

57. 插入区间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
    vector<vector<int>>results;
    int len = intervals.size();
    int left = 0,right = 0;
    bool placed = false;
    for(int i=0;i<len;i++){
        if(intervals[i][1] < newInterval[0]){       //无重叠,且在前面
            results.push_back(intervals[i]);
        }
        else if(intervals[i][0]>newInterval[1]){    //无重叠,且在后面
            if(!placed){
                results.push_back(newInterval);
                placed = true;
            }
            results.push_back(intervals[i]);
        }else{                                      //有重叠,更新重叠区间
            newInterval[0] = min(newInterval[0],intervals[i][0]);
            newInterval[1] = max(newInterval[1],intervals[i][1]);
        }
    }
    if(!placed){
        results.push_back(newInterval);
    }
    return results;
}