435. 無重疊區(qū)間

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

注意 只在一點上接觸的區(qū)間是 不重疊的。例如 [1, 2] 和 [2, 3] 是不重疊的。

示例 1:

輸入: intervals = [[1,2],[2,3],[3,4],[1,3]]
輸出: 1
解釋: 移除 [1,3] 后，剩下的區(qū)間沒有重疊。

示例 2:

輸入: intervals = [ [1,2], [1,2], [1,2] ]
輸出: 2
解釋: 你需要移除兩個 [1,2] 來使剩下的區(qū)間沒有重疊。

示例 3:

輸入: intervals = [ [1,2], [2,3] ]
輸出: 0
解釋: 你不需要移除任何區(qū)間，因為它們已經(jīng)是無重疊的了。

提示:

• 1 <= intervals.length <= 105
• intervals[i].length == 2
• -5 * 104 <= starti < endi <= 5 * 104

//easy，跟昨天的射氣球一樣的
class Solution {
public:int eraseOverlapIntervals(vector<vector<int>>& intervals) {// 這道題完全就是昨天寫的射氣球的變體，這里只需要求出非重疊區(qū)間的最大個數(shù)，就能得知需要移除的區(qū)間個數(shù)int sum = 0;sort(intervals.begin(), intervals.end(),[](vector<int>& a, vector<int>& b) { return a[1] < b[1]; });int line = INT_MIN;for (auto p : intervals) {if (p[0] >= line) {sum++;line = p[1];}}return intervals.size() - sum;}
};

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

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

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

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

示例 1：

輸入：s = "ababcbacadefegdehijhklij"
輸出：[9,7,8]
解釋：
劃分結果為 "ababcbaca"、"defegde"、"hijhklij" 。
每個字母最多出現(xiàn)在一個片段中。
像 "ababcbacadefegde", "hijhklij" 這樣的劃分是錯誤的，因為劃分的片段數(shù)較少。 

示例 2：

輸入：s = "eccbbbbdec"
輸出：[10]

提示：

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

分析：

構建字符的最后出現(xiàn)位置

• 使用一個 index 數(shù)組來記錄每個字符在字符串中最后一次出現(xiàn)的位置。也就是說，index[i] 存儲的是字符 s[i] 在 s 中的最后一個位置。
• 對于每個字符 s[i]，通過第二層循環(huán)從 i+1 到 n-1 遍歷，查找 s[i] 最后一次出現(xiàn)的索引，更新 index[i]。

遍歷并確定劃分的點

• 接下來，遍歷字符串的每個字符，維護一個 Max 變量記錄到當前位置為止的字符的最遠位置，即 Max = max(Max, index[i])。這個 Max 表示當前字符及其之前的所有字符可以在 Max 的范圍內(nèi)完全包含。
• 如果當前索引 i 與 Max 相等，說明從 start 到 i 這一段子串中的字符已經(jīng)全部處理完，可以作為一個獨立的子串，記錄其長度并更新 start 為 i。

class Solution {
public:vector<int> partitionLabels(string s) {//統(tǒng)計每個字符出現(xiàn)的最后位置，然后從頭開始遍歷，尋找最大的范圍，如果正遍歷到最大范圍，就是切割點vector<int> index(s.length(), 0);vector<int> result;for (int i = 0; i < s.length(); i++) {char c = s[i];int tmp = i;for (int j = i + 1; j < s.length(); j++) {if (c == s[j])tmp = j;}index[i] = tmp;}int Max = -1;int start = -1;//這里注意，題目求的是長度for (int i = 0; i < s.length(); i++) {Max = max(Max, index[i]);if (Max == i) {result.push_back(i - start);start = i;}}return result;}
};

但是，時間復雜度是O(N^2)，因為在確定字母出現(xiàn)的最后位置時，采用了兩層循環(huán)?？梢詢?yōu)化為O(N)。

class Solution {
public:vector<int> partitionLabels(string s) {// 記錄每個字符最后出現(xiàn)的位置vector<int> lastIndex(26, -1); // 記錄字符a到z的最后出現(xiàn)位置for (int i = 0; i < s.length(); i++) {lastIndex[s[i] - 'a'] = i;}vector<int> result;int start = 0, end = 0;for (int i = 0; i < s.length(); i++) {// 更新end為當前字符的最后出現(xiàn)位置end = max(end, lastIndex[s[i] - 'a']);// 如果當前索引i等于end，說明可以分割if (i == end) {result.push_back(i - start + 1);start = i + 1; // 更新start為下一個分割點的起始位置}}return result;}
};

56. 合并區(qū)間

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

示例 1：

輸入：intervals = [[1,3],[2,6],[8,10],[15,18]]
輸出：[[1,6],[8,10],[15,18]]
解釋：區(qū)間 [1,3] 和 [2,6] 重疊, 將它們合并為 [1,6].

示例 2：

輸入：intervals = [[1,4],[4,5]]
輸出：[[1,5]]
解釋：區(qū)間 [1,4] 和 [4,5] 可被視為重疊區(qū)間。

提示：

• 1 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 104

分析：

這題跟重疊區(qū)間，射氣球差不多。關鍵在于判斷重疊之后，要怎么處理。

class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {sort(intervals.begin(), intervals.end(),[](vector<int>& x,vector<int>& y) {return x[0]<y[0];});//按左邊界排序vector<vector<int>> res;res.push_back(intervals[0]);for(int i=0;i<intervals.size();i++) {if(res.back()[1]>=intervals[i][0]) {//重疊，合并res.back()[1]=max(res.back()[1],intervals[i][1]);}else//不重疊res.push_back(intervals[i]);}return res;}
};