代码随想录算法训练营Day30 | 452. 用最少数量的箭引爆气球 | 435. 无重叠区间 | 763.划分字母区间

今日任务

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

• 题目链接： https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/description/
• 题目描述：
  

Code

class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        ranges::sort(points, [&](auto &a, auto &b)->bool{
            return a[0] < b[0];
        });
        vector<vector<int>> ans = {points[0]};
        int n = points.size();
        for(int i = 1; i < n; i++){
            auto &back = ans.back();
            if(back[1] >= points[i][0]){
                back[0] = points[i][0];
                back[1] = back[1] > points[i][1] ? points[i][1] : back[1];
            }else{
                ans.push_back(points[i]);
            }
        }
        return ans.size();
    }
};

435. 无重叠区间

• 题目链接： https://leetcode.cn/problems/non-overlapping-intervals/description/
• 题目描述：
  

Code

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        // 排序end
        // ranges::sort(intervals, [](auto &a, auto &b)->bool{
        //     return a[1] < b[1];
        // });
        // int ans = 1;
        // int n = intervals.size();
        // // vector<int> pre = intervals[0];
        // int pre = intervals[0][1];
        // for(int i = 1; i < n; i++){
        //     int start = intervals[i][0], end = intervals[i][1];
        //     if(start >= pre){
        //        ans++;
        //        pre = end;
        //     }
        // }
        // return n - ans;

        // 排序start
        ranges::sort(intervals, [](auto &a, auto &b)->bool{
            return a[0] < b[0];
        });
        int ans = 1;
        int n = intervals.size();
        vector<int> pre = intervals[0];
        // int pre = intervals[0][1];
        for(int i = 1; i < n; i++){
            int start = intervals[i][0], end = intervals[i][1];
            if(start < pre[1]){
                pre[0] = start;
                pre[1] = min(pre[1], end);
            }else{
                pre = intervals[i];
                ans++;
            }
        }
        return n - ans;
    }
};

763.划分字母区间

• 题目链接： https://leetcode.cn/problems/partition-labels/description/
• 题目描述：
  

Code

class Solution {
public:
    vector<int> partitionLabels(string s) {
        vector<int> last_idx(26, -1);
        for(int i = 0; i < s.size(); i++){
            last_idx[s[i] - 'a'] = i;
        }
        vector<int> ans;
        // for(int i = 0, n = s.size(); i < n;){
        //     int start = i;
        //     int end = last_idx[s[i++] - 'a'];
        //     if(end == -1){
        //         continue;
        //     }
        //     while(i < n && i <= end){
        //         end = max(end, last_idx[s[i] - 'a']);
        //         i++;
        //     }
        //     ans.push_back(i - start);
        // }

        int start = 0, end = 0;
        for(int i = 0; i < s.size(); i++){
            end = max(end, last_idx[s[i] - 'a']);
            if(i == end){
                ans.push_back(i - start + 1);
                start = i + 1;
            }
        }
        return ans;
    }
};
```![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/5e3eaddd2410470d808594216c65b2a1.png)