算法训练（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;}
};