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

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

452. 用最少数量的箭引爆气球
排序后数组points = [[1,10],[3,9],[4,11],[6,7],[6,9],[8,12],[9,12]]

局部最优：尽可能多的气球重合，计算完全重叠的区间，在重合区间内射箭，可以一箭射爆这些重叠的气球；
比如：[[1,10],[3,9],[4,11],[6,7],[6,9]] 的重合区间为[6,7]；在这个区间内射箭可以一箭射爆全部气球；
全局最优：用最少的箭射爆全部气球；
注意：要求满足 Xstart ≤ X ≤ Xend，则该气球会被引爆；即[1,2],[2,3] 两只气球可以用同一支箭引爆；

class Solution {
public:static bool cmp (vector<int>& a, vector<int>& b) {// if (a[0] == b[0]) {//     return a[1] < b[1];// }return a[0] < b[0];}int findMinArrowShots(vector<vector<int>>& points) {sort(points.begin(), points.end(), cmp);int ans = 1;// 重合区间[start, end]int start = points[0][0];int end = points[0][1];for (int i = 1; i < points.size(); i++) {if (points[i][0] >= start && points[i][0] <= end) {if (points[i][1] <= end) {end = points[i][1];} start = points[i][0];} else if (points[i][0] > end) { // 区间不重合ans++;start = points[i][0];end = points[i][1];}}return ans;}
};

发现箭在边界也可以引爆气球，我们不需要维护一个重合区间，只要维护重合区间的右端点即可；因为右边界也是判断区间是否重合的关键；

for (int i = 1; i < points.size(); i++) {if (points[i][0] > end) { // 区间不重合ans++;end = points[i][1];}else if (points[i][1] < end) {end = points[i][1];}
}

右端点从小到大排序

class Solution {
public: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 ans = 1;int end = points[0][1];for (int i = 1; i < points.size(); i++) {if (points[i][0] > end) { // 区间不重合ans++;end = points[i][1];}}return ans;}
};

435. 无重叠区间

435. 无重叠区间
局部最优：在有重合的区间里找一个区间范围尽可能小的区间;
比如：[[1,10],[3,9],[4,11],[6,7],[6,9]] 的最小范围区间为[6,7]；
全局最优：最少的移除区间个数；

class Solution {
public:static bool cmp(vector<int>& a, vector<int>& b) {if(a[0] == b[0]) {return a[1] < b[1];}return a[0] < b[0];}int eraseOverlapIntervals(vector<vector<int>>& intervals) {sort(intervals.begin(), intervals.end(), cmp);int ans = 0;// 在有重合的区间里找一个区间范围尽可能小的区间[start, end]int start = intervals[0][0];int end = intervals[0][1];for (int i = 1; i < intervals.size(); i++) {if (intervals[i][0] >= start && intervals[i][0] < end){if(intervals[i][1] <= end) {start = intervals[i][0];end = intervals[i][1];}ans++;} else if (intervals[i][0] >= end) {start = intervals[i][0];end = intervals[i][1];}}return ans;}
};

763. 划分字母区间

763. 划分字母区间
知道每一个字母出现的区间，合并重叠空间，计算合并后区间的大小；

class Solution {
public:vector<int> partitionLabels(string s) {vector<int> vec(26, 0); // 存储每个字母最后出现的下标for (int i = 0; i < s.size(); i++) {vec[s[i] - 'a'] = i;}vector<int> ans;int start = 0;int end = 0;for (int i = 0; i < s.size(); i++) {end = max(end, vec[s[i] - 'a']); // 更新字符出现的最远边界if (end == i) { // 当前区间合并完毕ans.push_back(end - start + 1); // 区间长度加入答案start = i + 1; // 下一个区间的左端点}}return ans;}
};