算法训练（leetcode）第二十六天 | 452. 用最少数量的箭引爆气球、435. 无重叠区间、763. 划分字母区间

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

leetcode题目地址

思路一

先按起始坐标从小到大排序。排序后找交集并将交集存入一个数组中，遍历气球数组从交集数组中找交集，找到与当前集合相交的集合后将该集合的范围更新为两集合的交集（即左右区间取最小），最后返回交集数组的长度。

时间复杂度： $O(n^2)$
空间复杂度： $O(n)$

// c++
class Solution {
public: 
    static bool cmp(const vector<int> & a, const vector<int> & b){
        if(a[0] == b[0]) return a[1]>b[1];
        return a[0] < b[0];
    }
    int findMinArrowShots(vector<vector<int>>& points) {
        vector<vector<int>> arrows;
        sort(points.begin(), points.end(), cmp);
        for(int i=0; i<points.size(); i++){
            bool flag = true;
            for(int j=0; j<arrows.size(); j++){
                if(points[i][0]>=arrows[j][0] && points[i][0] <= arrows[j][1]){
                    arrows[j][0] = min(arrows[j][0], points[i][0]);
                    arrows[j][1] = min(arrows[j][1], points[i][1]);
                    flag = false;
                    break;
                }
            }
            if(flag){
                arrows.emplace_back(points[i]);
            }
        }
        return arrows.size();
    }
};

思路二

和思路一本质上是一样的，只是不再借助额外空间，也不再需要双层循环。排序后只查看当前气球的起始坐标小于上一个气球的结束坐标，是则说明有重叠，则缩小当前节点的结束坐标为交集的结束位置，反之没有重叠则箭数量+1。

时间复杂度： $O(nlogn)$
空间复杂度： $O(1)$

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

435. 无重叠区间

leetcode题目地址

本题可以说是和上一题换汤不换药，只不过上一题是统计不重叠的区间个数，本题是统计重叠区间。尽可能少的移除区间来保持剩余区间互不重叠，那每次出现重叠移除区间最大的那个即可。

时间复杂度： $O(nlogn)$
空间复杂度： $O(1)$

// c++
class Solution {
public:
    static bool cmp(const vector<int>&a, const vector<int>&b){
        if(a[0] == b[0]) return a[1]>b[1];
        return a[0]<b[0];
    }
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        int result = 0;
        sort(intervals.begin(), intervals.end(), cmp);
        for(int i=1; i<intervals.size(); i++){
            if(intervals[i][0] < intervals[i-1][1]){
                // 把最大的区间移除
                intervals[i][1] = min(intervals[i-1][1], intervals[i][1]);
                result++;
            }
        }
        return result;

    }
};

763. 划分字母区间

leetcode题目地址

记录每个字符出现的最远位置，子串截取到子串中出现的字符的最远位置。

时间复杂度： $O(n)$
空间复杂度： $O(1)$

// c++
class Solution {
public:
    vector<int> partitionLabels(string s) {
        cin.tie(nullptr)->sync_with_stdio(false);
        int hash[26] = {0};
        for(int i=0; i<s.size(); i++){
            hash[s[i]-'a'] = i;
        }
        int left = 0;
        int right = 0;
        vector<int> result;
        for(int i=0; i<s.size(); i++){
            right = max(right, hash[s[i]-'a']);
            if(i==right){
                result.emplace_back(right-left+1);
                left = i+1;
            }
        }
        return result;
    }
};