代码随想录训练营day30|贪心算法part4

用最少数量的箭引爆气球

力扣题目链接

class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        int result = 1;
        sort(points.begin(), points.end(),[](vector<int>& a, vector<int>& b){
            return (a[0] == b[0]) ? a[1] < b[1] : a[0] < b[0];
        });
        int arrow = points[0][1];
        for(auto p : points){
            // 能射爆新的气球
            if(p[0] <= arrow){
                arrow = min(arrow, p[1]);
            }
            // 不能射爆新的气球
            else{
                arrow = p[1];
                result++;
            }
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

无重叠区间

力扣题目链接

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        int result = 0;
        sort(intervals.begin(), intervals.end(), [](vector<int>& a, vector<int>& b){
            return (a[0] == b[0]) ? a[1] < b[1] : a[0] < b[0];
        });
        int r = intervals[0][0] - 1;
        for(vector<int> p : intervals){
            // 没有重合，移动右区间
            if(r <= p[0]){
                r = p[1];
            }
            // 重合时取小的右区间
            else{
                r = min(p[1], r);
                result++;
            }
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

划分字母区间

力扣题目链接

class Solution {
public:
    vector<int> partitionLabels(string s) {
        vector<vector<int>> positions(26, vector<int>(2, -1));
        for(int i = 0; i < s.length(); i++){
            if(positions[s[i] - 'a'][0] == -1){
                positions[s[i] - 'a'][0] = i;
                positions[s[i] - 'a'][1] = i;
            }
            else{
                positions[s[i] - 'a'][1] = i;
            }
        }
        sort(positions.begin(), positions.end(), [](vector<int>& a, vector<int>& b){
            return a[0] < b[0];
        });
        int l = 0;
        int r = -1;
        vector<int> result;
        for(int i = 0; i < 26; i++){
            if(positions[i][0] == -1)
                continue;
            if(r < positions[i][0] && r != -1){
                result.push_back(r-l+1);
                r = positions[i][1];
                l = positions[i][0];
            }
            else{
                r = max(r, positions[i][1]);
            }
        }
        result.push_back(r-l+1);
        return result;
    }
};
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
26
27
28
29
30
31
32
33
34
35