Day31- 贪心算法part05

一、无重叠区间

题目一：453. 无重叠区间?

435. 无重叠区间

给定一个区间的集合?intervals?，其中?intervals[i] = [starti, endi]?。返回?需要移除区间的最小数量，使剩余区间互不重叠?。

主要思想是优先保留结束时间早的区间，这样留给其他区间的空间就更多，从而减少需要移除的区间数量。具体做法是先根据每个区间的结束时间进行排序，然后遍历这些区间，每次选择结束时间最早且与前一个选中的区间不重叠的区间。

/*
 * @lc app=leetcode.cn id=435 lang=cpp
 *
 * [435] 无重叠区间
 */

// @lc code=start
class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if (intervals.empty()) return 0;

        sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[1] < b[1];
        });

        int count = 0; 
        int end = intervals[0][1]; 
        for (int i = 1; i < intervals.size(); ++i) {
            if (intervals[i][0] < end) {
                ++count;
            } else {
                end = intervals[i][1];
            }
        }

        return count;
    }
};
// @lc code=end

二、划分字母区间

题目一：763. 划分字母区间

763. 划分字母区间

给你一个字符串?s?。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是?s?。

返回一个表示每个字符串片段的长度的列表。

基本思路是首先遍历字符串，记录每个字符最后出现的位置。然后再次遍历字符串，使用一个变量来跟踪当前片段的结束位置。如果在遍历过程中遇到的任何字符的最后出现位置超过了当前片段的结束位置，就更新结束位置。一旦达到或超过当前片段的结束位置，就可以确定一个片段，并开始寻找下一个片段。

/*
 * @lc app=leetcode.cn id=763 lang=cpp
 *
 * [763] 划分字母区间
 */

// @lc code=start
class Solution {
public:
    vector<int> partitionLabels(string s) {
        vector<int> last(26, 0);
        int length = s.length();

        for (int i = 0; i < length; ++i) {
            last[s[i] - 'a'] = i;
        }

        vector<int> partition;
        int start = 0, end = 0;
        for (int i = 0; i < length; ++i) {
            end = max(end, last[s[i] - 'a']);
            if (i == end) {
                partition.push_back(end - start + 1);
                start = end + 1;
            }
        }
        return partition;
    }
};
// @lc code=end

三、合并区间

题目一：56. 合并区间

56. 合并区间

以数组?intervals?表示若干个区间的集合，其中单个区间为?intervals[i] = [starti, endi]?。请你合并所有重叠的区间，并返回?一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间?。

基本思路是先根据区间的起始位置进行排序，然后遍历排序后的区间列表，合并所有重叠的区间。

在这个算法中，首先对区间按起始位置进行排序。然后遍历每个区间，如果当前区间的起始位置大于已合并区间集合中最后一个区间的结束位置，则说明当前区间与已合并区间集合中的区间不重叠，可以直接添加到已合并区间集合中。如果有重叠，则将已合并区间集合中最后一个区间的结束位置更新为当前区间的结束位置和已合并区间集合中最后一个区间的结束位置中的较大值。

/*
 * @lc app=leetcode.cn id=56 lang=cpp
 *
 * [56] 合并区间
 */

// @lc code=start
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if (intervals.empty()) return {};

        sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[0] < b[0];
        });

        vector<vector<int>> merged;
        for (const auto& interval : intervals) {
            if (merged.empty() || merged.back()[1] < interval[0]) {
                merged.push_back(interval);
            } else {
                merged.back()[1] = max(merged.back()[1], interval[1]);
            }
        }

        return merged;
    }
};
// @lc code=end