2023年10月13日 - 贪心算法5

435. 无重叠区间

 class Solution {
 public:
     // 按照区间右边界排序
     static bool cmp (const vector<int>& a, const vector<int>& b) {
         return a[1] < b[1];
     }
     int eraseOverlapIntervals(vector<vector<int>>& intervals) {
         if (intervals.size() == 0) return 0;
         sort(intervals.begin(), intervals.end(), cmp);
         int count = 1; // 记录非交叉区间的个数
         int end = intervals[0][1]; // 记录区间分割点
         for (int i = 1; i < intervals.size(); i++) {
             if (end <= intervals[i][0]) {
                 end = intervals[i][1];
                 count++;
             }
         }
         return intervals.size() - count;
     }
 };

763. 划分字母区间

① 每个元素最远出现位置

② 遍历字符串，寻找分割点

 class Solution {
 public:
     vector<int> partitionLabels(string S) {
         int hash[27] = {0}; // i为字符，hash[i]为字符出现的最后位置
         for (int i = 0; i < S.size(); i++) { // 统计每一个字符最后出现的位置
             hash[S[i] - 'a'] = i;
         }
         vector<int> result;
         int left = 0;
         int right = 0;
         for (int i = 0; i < S.size(); i++) {
             right = max(right, hash[S[i] - 'a']); // 找到字符出现的最远边界
             if (i == right) {
                 result.push_back(right - left + 1);
                 left = i + 1;
             }
         }
         return result;
     }
 };

56. 合并区间

 class Solution {
 public:
     vector<vector<int>> merge(vector<vector<int>>& intervals) {
         vector<vector<int>> result;
         if (intervals.size() == 0) return result; // 区间集合为空直接返回
         // 排序的参数使用了lambda表达式
         sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b){return a[0] < b[0];});
 ​
         // 第一个区间就可以放进结果集里，后面如果重叠，在result上直接合并
         result.push_back(intervals[0]); 
 ​
         for (int i = 1; i < intervals.size(); i++) {
             if (result.back()[1] >= intervals[i][0]) { // 发现重叠区间
                 // 合并区间，只更新右边界就好，因为result.back()的左边界一定是最小值，因为我们按照左边界排序的
                 result.back()[1] = max(result.back()[1], intervals[i][1]); 
             } else {
                 result.push_back(intervals[i]); // 区间不重叠 
             }
         }
         return result;
     }
 };