一、無重疊區(qū)間

題目一：453. 無重疊區(qū)間?

435. 無重疊區(qū)間

給定一個區(qū)間的集合?intervals?，其中?intervals[i] = [starti, endi]?。返回?需要移除區(qū)間的最小數(shù)量，使剩余區(qū)間互不重疊?。

主要思想是優(yōu)先保留結(jié)束時間早的區(qū)間，這樣留給其他區(qū)間的空間就更多，從而減少需要移除的區(qū)間數(shù)量。具體做法是先根據(jù)每個區(qū)間的結(jié)束時間進行排序，然后遍歷這些區(qū)間，每次選擇結(jié)束時間最早且與前一個選中的區(qū)間不重疊的區(qū)間。

/*
 * @lc app=leetcode.cn id=435 lang=cpp
 *
 * [435] 無重疊區(qū)間
 */

// @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

二、劃分字母區(qū)間

題目一：763. 劃分字母區(qū)間

763. 劃分字母區(qū)間

給你一個字符串?s?。我們要把這個字符串劃分為盡可能多的片段，同一字母最多出現(xiàn)在一個片段中。

注意，劃分結(jié)果需要滿足：將所有劃分結(jié)果按順序連接，得到的字符串仍然是?s?。

返回一個表示每個字符串片段的長度的列表。

基本思路是首先遍歷字符串，記錄每個字符最后出現(xiàn)的位置。然后再次遍歷字符串，使用一個變量來跟蹤當(dāng)前片段的結(jié)束位置。如果在遍歷過程中遇到的任何字符的最后出現(xiàn)位置超過了當(dāng)前片段的結(jié)束位置，就更新結(jié)束位置。一旦達到或超過當(dāng)前片段的結(jié)束位置，就可以確定一個片段，并開始尋找下一個片段。

/*
 * @lc app=leetcode.cn id=763 lang=cpp
 *
 * [763] 劃分字母區(qū)間
 */

// @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

三、合并區(qū)間

題目一：56. 合并區(qū)間

56. 合并區(qū)間

以數(shù)組?intervals?表示若干個區(qū)間的集合，其中單個區(qū)間為?intervals[i] = [starti, endi]?。請你合并所有重疊的區(qū)間，并返回?一個不重疊的區(qū)間數(shù)組，該數(shù)組需恰好覆蓋輸入中的所有區(qū)間?。

基本思路是先根據(jù)區(qū)間的起始位置進行排序，然后遍歷排序后的區(qū)間列表，合并所有重疊的區(qū)間。

在這個算法中，首先對區(qū)間按起始位置進行排序。然后遍歷每個區(qū)間，如果當(dāng)前區(qū)間的起始位置大于已合并區(qū)間集合中最后一個區(qū)間的結(jié)束位置，則說明當(dāng)前區(qū)間與已合并區(qū)間集合中的區(qū)間不重疊，可以直接添加到已合并區(qū)間集合中。如果有重疊，則將已合并區(qū)間集合中最后一個區(qū)間的結(jié)束位置更新為當(dāng)前區(qū)間的結(jié)束位置和已合并區(qū)間集合中最后一個區(qū)間的結(jié)束位置中的較大值。文章來源地址http://www.zghlxwxcb.cn/news/detail-805472.html

/*
 * @lc app=leetcode.cn id=56 lang=cpp
 *
 * [56] 合并區(qū)間
 */

// @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

到了這里，關(guān)于Day31- 貪心算法part05的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！