在二維空間中有許多球形的氣球。對于每個氣球，提供的輸入是水平方向上，氣球直徑的開始和結束坐標。由于它是水平的，所以縱坐標并不重要，因此只要知道開始和結束的橫坐標就足夠了。開始坐標總是小于結束坐標。

一支弓箭可以沿著 x 軸從不同點完全垂直地射出。在坐標 x 處射出一支箭，若有一個氣球的直徑的開始和結束坐標為 xstart，xend， 且滿足 ?xstart?≤ x ≤ xend，則該氣球會被引爆。可以射出的弓箭的數量沒有限制。 弓箭一旦被射出之后，可以無限地前進。我們想找到使得所有氣球全部被引爆，所需的弓箭的最小數量。

給你一個數組 points ，其中 points [i] = [xstart,xend] ，返回引爆所有氣球所必須射出的最小弓箭數。

示例 1：

• 輸入：points = [[10,16],[2,8],[1,6],[7,12]]
• 輸出：2
• 解釋：對于該樣例，x = 6 可以射爆 [2,8],[1,6] 兩個氣球，以及 x = 11 射爆另外兩個氣球

按照起始位置排序，那么就從前向后遍歷氣球數組，靠左盡可能讓氣球重復。

從前向后遍歷遇到重疊的氣球了怎么辦？

如果氣球重疊了，重疊氣球中右邊邊界的最小值 之前的區間一定需要一個弓箭。

重點：如何更新重疊的區間的右邊界，見注釋：

class Solution {
public:static bool cmp(const vector<int>& a, const vector<int>& b) {return a[0] < b[0]; // 左邊界排序}int findMinArrowShots(vector<vector<int>>& points) {if (points.size() == 0) return 0;sort(points.begin(), points.end(), cmp); // 按照左邊界從小到大排序int result = 1; // points 不為空至少需要一支箭for (int i = 1; i < points.size(); i++) {if (points[i][0] > points[i - 1][1]) {  // 氣球i左邊界>氣球i-1右邊界，無重疊result++; // 前面的箭已經算過了，由于無重疊，后面需要一支新的箭}else { // 氣球i左邊界<=氣球i-1右邊界，有重疊，更新氣球i邊界，方便下一輪比較// 取最小是因為看最差的情況下，會不會有第三個和前兩個有重疊，方便后續判斷points[i][1] = min(points[i][1], points[i - 1][1]); }}return result;}
};

給定一個區間的集合，找到需要移除區間的最小數量，使剩余區間互不重疊。

注意: 可以認為區間的終點總是大于它的起點。 區間 [1,2] 和 [2,3] 的邊界相互“接觸”，但沒有相互重疊。

示例 1:

• 輸入: [ [1,2], [2,3], [3,4], [1,3] ]
• 輸出: 1
• 解釋: 移除 [1,3] 后，剩下的區間沒有重疊。

示例 2:

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

核心代碼：intervals[i][1] = min(intervals[i - 1][1], intervals[i][1]);

當兩個區間 [i-1] 和 [i] 重疊時，我們選擇保留結束時間更早的那個區間，為后面的區間騰空間。因為越早結束，越不容易和后面的區間重疊！！！

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 count = 0; // 注意這里從0開始，因為是記錄重疊區間for (int i = 1; i < intervals.size(); i++) {if (intervals[i][0] < intervals[i - 1][1]) { //重疊情況intervals[i][1] = min(intervals[i - 1][1], intervals[i][1]);count++;}}return count;}
};

本題其實和452.用最少數量的箭引爆氣球?(opens new window)非常像，弓箭的數量就相當于是非交叉區間的數量，只要把弓箭那道題目代碼里射爆氣球的判斷條件加個等號（認為[0，1][1，2]不是相鄰區間），然后用總區間數減去弓箭數量 就是要移除的區間數量了。

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 result = 1; // points 不為空至少需要一支箭for (int i = 1; i < intervals.size(); i++) {if (intervals[i][0] >= intervals[i - 1][1]) {result++; // 需要一支箭}else {  // 氣球i和氣球i-1挨著intervals[i][1] = min(intervals[i - 1][1], intervals[i][1]); // 更新重疊氣球最小右邊界}}return intervals.size() - result;}
};

3.763劃分字母區間763. 劃分字母區間 - 力扣（LeetCode）

字符串 S 由小寫字母組成。我們要把這個字符串劃分為盡可能多的片段，同一字母最多出現在一個片段中。返回一個表示每個字符串片段的長度的列表。

示例：

• 輸入：S = "ababcbacadefegdehijhklij"
• 輸出：[9,7,8] 解釋： 劃分結果為 "ababcbaca", "defegde", "hijhklij"。 每個字母最多出現在一個片段中。 像 "ababcbacadefegde", "hijhklij" 的劃分是錯誤的，因為劃分的片段數較少。

在遍歷的過程中相當于是要找每一個字母的邊界，如果找到之前遍歷過的所有字母的最遠邊界，說明這個邊界就是分割點了。此時前面出現過所有字母，最遠也就到這個邊界了。

可以分為如下兩步：

• 統計每一個字符最后出現的位置
• 從頭遍歷字符，并更新字符的最遠出現下標，如果找到字符最遠出現位置下標和當前下標相等了，則找到了分割點，如圖

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;}
};