Leetcode?435. 無重疊區(qū)間

題目鏈接：435 無重疊區(qū)間

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

思考：貪心法。和452 用最少數(shù)量的箭引爆氣球原理類似。按照左邊界排序，從左向右記錄多余交叉區(qū)間的個(gè)數(shù)?；蛘甙凑沼疫吔缗判?#xff0c;從左向右記錄非交叉區(qū)間的個(gè)數(shù)。最后用區(qū)間總數(shù)減去非交叉區(qū)間的個(gè)數(shù)就是需要移除的區(qū)間的個(gè)數(shù)。

此圖先按右邊界排序，之后記錄非交叉區(qū)間的個(gè)數(shù)還是有技巧的。取 區(qū)間1 和 區(qū)間2 右邊界的最小值，因?yàn)檫@個(gè)最小值之前的部分一定是 區(qū)間1 和區(qū)間2 的重合部分，如果這個(gè)最小值也觸達(dá)到區(qū)間3，那么說明 區(qū)間 1，2，3都是重合的。

代碼一（按右邊界排序）：

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;     //記錄非重疊區(qū)間個(gè)數(shù)int end = intervals[0][1];      //記錄當(dāng)前重疊區(qū)間右邊界for (int i = 1; i < intervals.size(); i++) {if (intervals[i][0] >= intervals[i - 1][1])count++;elseintervals[i][1] = min(intervals[i][1], intervals[i - 1][1]);        //更新重疊區(qū)間右邊界}return intervals.size() - count;}
};

代碼二（按左邊界排序）：

class Solution {
public:static bool cmp(const vector<int>& a, const vector<int>& b) {return a[0] < b[0];     //按左邊界排序}int eraseOverlapIntervals(vector<vector<int>>& intervals) {if (intervals.size() == 0)  return 0;sort(intervals.begin(), intervals.end(), cmp);      //排序int result = 0;     //記錄多余重疊區(qū)間個(gè)數(shù)for (int i = 1; i < intervals.size(); i++) {if (intervals[i][0] < intervals[i - 1][1]) {        //存在重疊區(qū)間intervals[i][1] = min(intervals[i][1], intervals[i - 1][1]);        //更新重疊區(qū)間右邊界result++;}}return result;}
};

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

題目鏈接：763 劃分字母區(qū)間

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

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

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

• 1 <= s.length <= 500
• s?僅由小寫英文字母組成

思考：貪心法。先尋找所有字母的最后出現(xiàn)的下標(biāo)位置，和其首次出現(xiàn)的位置形成區(qū)間。接下來將重疊的區(qū)間合并起來，并記錄每個(gè)不重疊區(qū)間的大小。由于按順序遍歷字符串因此在合并區(qū)間時(shí)只需要更新右邊界，在不重疊時(shí)初始化新區(qū)間的邊界。

代碼：

class Solution {
public:vector<int> partitionLabels(string s) {int lastPresence[27] = { 0 };       //記錄所有字母最后出現(xiàn)的下標(biāo)位置for (int i = 0; i < s.size(); i++)      lastPresence[s[i] - 'a'] = i;int left = 0;       //記錄區(qū)間的左邊界int right = 0;      //記錄區(qū)間的右邊界vector<int> result;for (int i = 0; i < s.size(); i++) {right = max(right, lastPresence[s[i] - 'a']);       //更新當(dāng)前區(qū)間右邊界if (i == right) {result.push_back(right - left + 1);left = i + 1;       //新區(qū)間左邊界}}return result;}
};

Leetcode?56. 合并區(qū)間

題目鏈接：56 合并區(qū)間

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

思考：貪心法。本題和435. 無重疊區(qū)間非常相似，都是先排序后再處理。區(qū)別：處理過程中如果記錄區(qū)間和當(dāng)前處理區(qū)間存在重疊，則更新記錄區(qū)間的右邊界，否則記錄當(dāng)前處理區(qū)間。

代碼：

class Solution {
public:static bool cmp(const vector<int>& a, const vector<int>& b) {return a[0] < b[0];     //按左區(qū)間排序}vector<vector<int>> merge(vector<vector<int>>& intervals) {vector<vector<int>> result;if (intervals.size() == 0)  return result;sort(intervals.begin(), intervals.end(), cmp);result.push_back(intervals[0]);     //將首個(gè)區(qū)間放入結(jié)果集，后面出現(xiàn)重疊則修改右邊界for (int i = 1; i < intervals.size(); i++) {if (result.back()[1] >= intervals[i][0])result.back()[1] = max(result.back()[1], intervals[i][1]);      //更新重疊區(qū)間右邊界elseresult.push_back(intervals[i]);     //區(qū)間不重疊則加入新區(qū)間}return result;}
};

自我總結(jié)：

• 逐步理解貪心法處理區(qū)間問題，排序+特殊處理。