前言

之前覺得貪心思想，根本就總結不出一種規律，雖然這種題思想都是一個，但是，情況太多了，感覺這種題，很難想到，要不就是常識，要不想都想不到，這種題就是要看自己有沒有刷過，并且還要能記住，

但是，細細體會，才會讓你跟好的理解這種題的解題思路，至少，能讓你很好的理解你刷的貪心題目，

貪心思想：

區域最優，推匯出全域最優，

簡單點說就是，每一次都取得最優的結果，最終的結果一定就會得到最優的結果，

比如：有很多鈔票，規定次數，最后得到價值最大，解法：就是，每一次拿價值最大的鈔票(區域最優)，最后價值會最大(全域最優)，

主要就是想到，區域最優，

題目

基礎

455. 分發餅干

假設你是一位很棒的家長，想要給你的孩子們一些小餅干，但是，每個孩子最多只能給一塊餅干，

對每個孩子 i，都有一個胃口值 g[i]，這是能讓孩子們滿足胃口的餅干的最小尺寸；并且每塊餅干 j，都有一個尺寸 s[j] ，如果 s[j] >= g[i]，我們可以將這個餅干 j 分配給孩子 i ，這個孩子會得到滿足，你的目標是盡可能滿足越多數量的孩子，并輸出這個最大數值，

示例 1:

輸入: g = [1,2,3], s = [1,1]
輸出: 1
解釋:
你有三個孩子和兩塊小餅干，3個孩子的胃口值分別是：1,2,3，
雖然你有兩塊小餅干，由于他們的尺寸都是1，你只能讓胃口值是1的孩子滿足，
所以你應該輸出1，

區域最優：每一次都拿最大的餅干，去喂給胃口最大，并且可以滿足的孩子，

整體最優：滿足孩子數最多，

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        //貪心，將最大的餅干給胃口最大，并且能滿足的孩子
        //排序，最大在后面，最小在前面
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());

        int len1 = g.size();
        int len2 = s.size();
        int count = 0;
        int j = len1-1;
        for(int i =len2-1; i>=0; i--){
            //找胃口最大的
            for(; j>=0; j--){
                if(g[j] <= s[i]){
                    //找到
                    count++;
                    j--;
                    break;
                }
            }
            if(j < 0){
                //沒有學生了
                break;
            }
            
        }

        return count;
        
    }
};

擺動序列

376. 擺動序列

如果連續數字之間的差嚴格地在正數和負數之間交替，則數字序列稱為 擺動序列 ，第一個差（如果存在的話）可能是正數或負數，僅有一個元素或者含兩個不等元素的序列也視作擺動序列，

例如， [1, 7, 4, 9, 2, 5] 是一個 擺動序列 ，因為差值 (6, -3, 5, -7, 3) 是正負交替出現的，

相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是擺動序列，第一個序列是因為它的前兩個差值都是正數，第二個序列是因為它的最后一個差值為零，
子序列 可以通過從原始序列中洗掉一些（也可以不洗掉）元素來獲得，剩下的元素保持其原始順序，

給你一個整數陣列 nums ，回傳 nums 中作為 擺動序列 的 最長子序列的長度 ，

示例 1：

輸入：nums = [1,7,4,9,2,5]
輸出：6
解釋：整個序列均為擺動序列，各元素之間的差值為 (6, -3, 5, -7, 3) ，

畫成圖，情況會是這樣：

區域最優：找到單調序列里的最大值和最小值，即洗掉單調序列里的中間值，

整體最優：擺動序列長度最長，

特殊情況：

根據題意，陣列只有一個或者兩個元素也構成擺動序列，于是需要定起始就有一個擺動序列，

并且：

解法：比較前后差值，正負交替，或者前面為0，擺動序列數加1，

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        //貪心思想，區域最優，找到單調的最高和最低點、洗掉單調不是最高最低點的值，
        //整體才能得到最大長度
        int res = 1;//只有一個值的情況
        int len = nums.size();
        if(len == 1){
            return res;
        }
        //first最低點前一個差值
        int first = nums[1] - nums[0];
        //兩個值的情況
        if(first){
            res++;
        }
        //最高點差值
        int second = 0;
        for(int i=2; i<len; i++){
            //找最高點
            second = nums[i] - nums[i-1];
            if((first <= 0 &&second > 0)||(first >= 0 && second < 0)){
                //更新最低點
                first = second;
                res++;
            }
            
        }

        return res;
    }
};

最大子序和

53. 最大子序和

給定一個整數陣列 nums ，找到一個具有最大和的連續子陣列（子陣列最少包含一個元素），回傳其最大和，

示例 1：

輸入：nums = [-2,1,-3,4,-1,2,1,-5,4]
輸出：6
解釋：連續子陣列 [4,-1,2,1] 的和最大，為 6 ，

區域最優：找到每一次正數和的最大值，

當和加到為負數時，這個和成為了下一次和的負擔，會拖累下一次的總和，需要從0開始加，

整體最優：找到整體最大和，

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int res = INT_MIN;
        int sum = 0;

        for(int i= 0; i<nums.size(); i++){
            sum+=nums[i];
            //最大子序和
            if(sum > res){
                res = sum;
            }
            //和為負數，需要從0開始加
            if(sum < 0){
                sum=0;
            }
        }

        return res;

    }
};

股票的最大利潤

股票的最大利潤

假設把某股票的價格按照時間先后順序存盤在陣列中，請問買賣該股票一次可能獲得的最大利潤是多少？

示例 1:

輸入: [7,1,5,3,6,4]
輸出: 5
解釋: 在第 2 天（股票價格 = 1）的時候買入，在第 5 天（股票價格 = 6）的時候賣出，最大利潤 = 6-1 = 5 ，
注意利潤不能是 7-1 = 6, 因為賣出價格需要大于買入價格，

注意：只能一次買賣，

貪心演算法：

區域最優：每次選出前面的最小買入價格，當前賣出，每次當前值和最小賣出價格的利潤的最大值，

全域最優：得到最大利潤，

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        //最小買入點
        int pmin = INT_MAX;
        //最大利潤
        int pmax = 0;

        int len = prices.size();
        for(int i =0; i<len; i++){
            //找前面最小買入點
            if(pmin > prices[i]){
                pmin = prices[i];
            }
            //當前賣出的最大利潤
            if(pmax < prices[i] - pmin){
                pmax = prices[i] - pmin;
            }

        }

        return pmax;

    }
};

買賣股票的最佳時機II

122. 買賣股票的最佳時機 II

給定一個陣列 prices ，其中 prices[i] 是一支給定股票第 i 天的價格，

設計一個演算法來計算你所能獲取的最大利潤，你可以盡可能地完成更多的交易（多次買賣一支股票），

注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票），

示例 1:

輸入: prices = [7,1,5,3,6,4]
輸出: 7
解釋: 在第 2 天（股票價格 = 1）的時候買入，在第 3 天（股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 ，
隨后，在第 4 天（股票價格 = 3）的時候買入，在第 5 天（股票價格 = 6）的時候賣出, 這筆交易所能獲得利潤 = 6-3 = 3 ，

貪心演算法：

區域最優：在最低是買入，在最高時賣出，完后如此回圈，

全域最優：會得到最大的利潤，

怎么才是最高和最低呢？

在一段區間內，單調遞增，找到最高點和最低點，計算差值，

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        //貪心演算法

        int res = 0;
        int i = 1;
        while(i<prices.size()){
            if(prices[i] > prices[i-1]){
                //最低價格
                int minprice = prices[i-1];
                while(i< prices.size() && prices[i] > prices[i-1]){
                    i++;
                }
                //最高價格
                int maxprice = prices[i-1];
                //得到一段區間的最大利潤
                res += (maxprice - minprice);
            }
            else{
                i++;
            }
        }

        return res;

    }
};

但是，其實，我們可以將每一個利潤進行分解，分解成每天的利潤，

比如：要求prices[3] - prices[0]的利潤，可以分解成prices[3] - prices[2] + prices[2] - prices[1] + prices[1] - prices[0]，

要求單調遞增的最大值和最小值的差，由于是單調遞增，每天的利潤一定會是正利潤，將所有的正利潤加起來就好了，

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        //貪心演算法
        //區域最優：獲得每天的 正利潤
        //整體最優：得到最大利潤
        int res = 0;
        int money = 0;
        for(int i =1; i<prices.size(); i++){
            if(prices[i] - prices[i-1] > 0){
                res += (prices[i] - prices[i-1]);
            }
        }

        return res;

    }
};

跳躍游戲

給定一個非負整數陣列 nums ，你最初位于陣列的 第一個下標 ，

陣列中的每個元素代表你在該位置可以跳躍的最大長度，

判斷你是否能夠到達最后一個下標，

示例 1：

輸入：nums = [2,3,1,1,4]
輸出：true
解釋：可以先跳 1 步，從下標 0 到達下標 1, 然后再從下標 1 跳 3 步到達最后一個下標，

區域最優：選出當前范圍內，下一次可以走的最大范圍，

全域最優：得到最大范圍，

結果：比較最大范圍是否包含nums的最后一個下標，

范圍就是索引對應索引對應的值，即i + nums[i]，

class Solution {
public:
    bool canJump(vector<int>& nums) {
        //貪心演算法；
        //區域最優：每次都選步數范圍內的最大步數，
        
        int len = nums.size();
        int i = 0;
        while(i < len){
            int maxstep = i + nums[i];
            //可以到達最后一個下標
            if(maxstep >= len - 1){
                return true;
            }
            //不可以到達最后一個下標
            //nums[i] = 0
            if(i == maxstep){
                return false;   
            }
            //選最大范圍，范圍等于j + nums[j]
            int m = -1;
            for(int j = i+1; j <= maxstep; j++){
                if(m < j + nums[j]){
                    i = j;
                    m = j + nums[j];
                }
            }

        }
        return true;
    }
};

跳躍游戲II

給你一個非負整數陣列 nums ，你最初位于陣列的第一個位置，

陣列中的每個元素代表你在該位置可以跳躍的最大長度，

你的目標是使用最少的跳躍次數到達陣列的最后一個位置，

假設你總是可以到達陣列的最后一個位置，

示例 1:

輸入: nums = [2,3,1,1,4]
輸出: 2
解釋: 跳到最后一個位置的最小跳躍數是 2，
從下標為 0 跳到下標為 1 的位置，跳 1 步，然后跳 3 步到達陣列的最后一個位置，

和上面一題如出一轍，不同的是，這一次肯定可以到達最后一個下標處，記錄步數，

區域最優：選出當前范圍內，下一次可以走的最大范圍，

全域最優：得到最小步數，

范圍就是索引對應索引對應的值，即i + nums[i]，

class Solution {
public:
    int jump(vector<int>& nums) {
        int len = nums.size();
        //不需要跳
        if(len == 1){
            return 0;
        }
        int i = 0;
        //初始化為1，最后一跳
        int step = 1;
        while(i < len){
            //最大范圍
            int maxcover = i + nums[i];
            //到達最后一個下標
            if(maxcover >= len - 1){
                break;
            }
            //找最大范圍
            int m = -1;
            for(int j = i+1; j <= maxcover; j++){
                if(m < j + nums[j]){
                    i = j;
                    m = j + nums[j];
                }
            }
            //步數加1
            step++; 

        }
        return step;

    }
};

K次取反后最?化的陣列和

K次取反后最?化的陣列和

給你一個整數陣列 nums 和一個整數 k ，按以下方法修改該陣列：

選擇某個下標 i 并將 nums[i] 替換為 -nums[i] ，
重復這個程序恰好 k 次，可以多次選擇同一個下標 i ，

以這種方式修改陣列后，回傳陣列 可能的最大和 ，

示例 1：

輸入：nums = [4,2,3], k = 1
輸出：5
解釋：選擇下標 1 ，nums 變為 [4,-2,3] ，

貪心演算法：

注意：數字可以重復選取，

區域最優：每次讓負數轉變為正數，如果為0并且沒有負數，讓0變符號K次，

整體最優：得到的陣列和為最大值，

當上面變化完之后，K還是大于0，還需要使用貪心演算法，

注意：上面情況變化完之后，沒有負數了，

區域最優：如果K為負數，讓最小值為負數，意思就是讓最小值變化符號K次，

整體最優：陣列和最大，

注意：再變符號前，先將陣列排好序，

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int len = nums.size();

        for(int i =0; i<len; i++){
            //如果是負數，變為正數
            if(k && nums[i] < 0){
                k--;
                nums[i] = -nums[i];
                continue;
            }
            //如果是0,只讓0變化就好了
            if(nums[i] == 0){
                k=0;
                break;
            }

        }
        //如果此時K>0且k為奇數，讓最小值為負數就好了
        if(k % 2){
            
            int min = INT_MAX;
            int pos = 0;
            for(int i =0; i<len; i++){
                if(min > nums[i]){
                    min = nums[i];
                    pos = i;
                }
            }
            nums[pos] = -nums[pos];
        }
        //求和
        int sum = 0;
        for(auto ch : nums){
            sum += ch;
        }
        return sum;
    }
};

加油站

加油站

在一潭訓路上有 N 個加油站，其中第 i 個加油站有汽油 gas[i] 升，

你有一輛油箱容量無限的的汽車，從第 i 個加油站開往第 i+1 個加油站需要消耗汽油 cost[i] 升，你從其中的一個加油站出發，開始時油箱為空，

如果你可以繞環路行駛一周，則回傳出發時加油站的編號，否則回傳 -1，

說明:

如果題目有解，該答案即為唯一答案，
輸入陣列均為非空陣列，且長度相同，
輸入陣列中的元素均為非負數，
示例 1:

輸入:
gas = [1,2,3,4,5]
cost = [3,4,5,1,2]

輸出: 3

解釋:
從 3 號加油站(索引為 3 處)出發，可獲得 4 升汽油，此時油箱有 = 0 + 4 = 4 升汽油
開往 4 號加油站，此時油箱有 4 - 1 + 5 = 8 升汽油
開往 0 號加油站，此時油箱有 8 - 2 + 1 = 7 升汽油
開往 1 號加油站，此時油箱有 7 - 3 + 2 = 6 升汽油
開往 2 號加油站，此時油箱有 6 - 4 + 3 = 5 升汽油
開往 3 號加油站，你需要消耗 5 升汽油，正好足夠你回傳到 3 號加油站，
因此，3 可為起始索引，

首先考慮清除，什么情況可以繞環路行駛一周，當消耗汽油和加的汽油數的差之和大于等于0時，說明可以環路一周，

起始位置怎么求，從0開始，走過一個站的剩余油數和小于0，說明不能做起始位置，

貪心演算法：

區域最優：從0站開始，走到j站的剩余油數小于0，說明j不能做起始位置，起始位置從j+1開始，并且，剩余油數從j+1開始加，

全域最優：找到可以跑一圈的起始位置，

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int len1 = gas.size();
        int len2 = cost.size();

        int sumrest = 0;//剩余總和
        int rest = 0;//當前剩余汽油
        int startpos = 0;//起始位置
        for(int i =0; i<len1; i++){
            sumrest += (gas[i] - cost[i]);
            rest += (gas[i] - cost[i]);
            //剩余汽油小于0，不能作為起始位置，起始位置在下一個
            if(rest < 0){
                rest = 0;
                startpos = i + 1;
            }
        }
        //sumrest >= 0說明可以環路一周
        if(sumrest >= 0){
            return startpos;
        }
        
        return -1;

    }
};

檸檬?找零

檸檬?找零

在檸檬水攤上，每一杯檸檬水的售價為 5 美元，顧客排隊購買你的產品，（按賬單 bills 支付的順序）一次購買一杯，

每位顧客只買一杯檸檬水，然后向你付 5 美元、10 美元或 20 美元，你必須給每個顧客正確找零，也就是說凈交易是每位顧客向你支付 5 美元，

注意，一開始你手頭沒有任何零錢，

給你一個整數陣列 bills ，其中 bills[i] 是第 i 位顧客付的賬，如果你能給每位顧客正確找零，回傳 true ，否則回傳 false ，

示例 1：

輸入：bills = [5,5,5,10,20]
輸出：true
解釋：
前 3 位顧客那里，我們按順序收取 3 張 5 美元的鈔票，
第 4 位顧客那里，我們收取一張 10 美元的鈔票，并返還 5 美元，
第 5 位顧客那里，我們找還一張 10 美元的鈔票和一張 5 美元的鈔票，
由于所有客戶都得到了正確的找零，所以我們輸出 true，

注意：是順序收取，

一開始沒有零錢，一開始賣出，收到的必須是5塊，

有三種情況：

1. 收到5塊，不需要找零，直接收取，

2. 收到10塊，需要找零5塊，

3. 收到20塊，需要找零15塊，

貪心思想：

區域最優：如果收到20塊錢，優先找零10塊和5塊，因為5塊的用處比10塊多，

全域最優：可以找零成功

class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        int fivecount = 0;
        int tencount = 0;
        int twcount = 0;
        
        int len = bills.size();
        if(bills[0] != 5){
            return false;
        }

        for(int i =0; i < len; i++){
                if(bills[i] == 5){
                    fivecount++;
                }
                else if(bills[i] == 10){
                    if(fivecount == 0){
                        return false;
                    }
                    else{
                        tencount++;
                        fivecount--;
                    }
                }
                else{
                    //bills[i] == 20
                    if(tencount > 0 && fivecount > 0){
                        //先還10塊加5塊的，5塊用處更多
                        tencount--;
                        fivecount--;
                        twcount++;
                    }
                    else if(fivecount >= 3){
                        fivecount -= 3;
                        twcount++;
                    }
                    else{
                        return false;
                    }
                }
        }
        return true;

    }
};

根據身?重建佇列

根據身?重建佇列

假設有打亂順序的一群人站成一個佇列，陣列 people 表示佇列中一些人的屬性（不一定按順序），每個 people[i] = [hi, ki] 表示第 i 個人的身高為 hi ，前面 正好 有 ki 個身高大于或等于 hi 的人，

請你重新構造并回傳輸入陣列 people 所表示的佇列，回傳的佇列應該格式化為陣列 queue ，其中 queue[j] = [hj, kj] 是佇列中第 j 個人的屬性（queue[0] 是排在佇列前面的人），

示例 1：

輸入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
輸出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
解釋：
編號為 0 的人身高為 5 ，沒有身高更高或者相同的人排在他前面，
編號為 1 的人身高為 7 ，沒有身高更高或者相同的人排在他前面，
編號為 2 的人身高為 5 ，有 2 個身高更高或者相同的人排在他前面，即編號為 0 和 1 的人，
編號為 3 的人身高為 6 ，有 1 個身高更高或者相同的人排在他前面，即編號為 1 的人，
編號為 4 的人身高為 4 ，有 4 個身高更高或者相同的人排在他前面，即編號為 0、1、2、3 的人，
編號為 5 的人身高為 7 ，有 1 個身高更高或者相同的人排在他前面，即編號為 1 的人，
因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新構造后的佇列，

這個題有兩個維度，一個維度是身高，一個維度是前面大于當前身高的人數，

我們需要先確定一個維度，通過另外一個維度來得到結果，

那我們是先確定身高還是人數呢？

如果確定人數，按照k從大到小排列，我們發現，身高仍會是無序的，并沒有確定好一個條件，

先確定好身高，按照身高從高到低排列，身高相同，人數少的排前面，此時，就只需要按照K來進行排列就好了，

看下圖：

此時，我們只需要按照K來進行插入到對應值的位置，前面高于當前身高的人數一定是正確的，

我們需要從大到小來進行插入，先處理好高身高的人，

貪心思想：

前提：按照身高從大到小排列，身高相同，人數少的排前面，

區域最優：按照人數，插入到對應位置，

全域最優：形成正確排列，

class Solution {
    static bool cmp(vector<int>& p1, vector<int>& p2){
        return p1[0] > p2[0] || (p1[0] == p2[0] && p1[1] < p2[1]);
    }
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
   
        int row = people.size();
        vector<vector<int>> res;
        
        sort(people.begin(), people.end(), cmp);

        for(int i=0; i<row; i++){
            //res[people[i][1]] = people[i];
            //vector<int> tmp = people[i];
            //people.erase(people.begin() + i);
            //people.insert(people.begin() + tmp[1], tmp);
            //cout<<i<<endl;
            res.insert(res.begin() + people[i][1], people[i]);
            //cout<<i<<endl;
        }

        return res;
    }
};

我們知道陣列插入資料，需要挪動資料，效率不是很高，而鏈表插入資料可以直接插入，

我們可以先用鏈表來形成佇列，

class Solution {
    static bool cmp(vector<int>& p1, vector<int>& p2){
        return p1[0] > p2[0] || (p1[0] == p2[0] && p1[1] < p2[1]);
    }
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        //先將ki為0，且最小的排前面
        int row = people.size();
        //不需要初始化
        list<vector<int>> ls;
        
        sort(people.begin(), people.end(), cmp);
        //從身高高的開始插入，按照k插入
        //前面會正好
        for(int i=0; i<row; i++){
            auto it = ls.begin();
            int pos = people[i][1];
            
            //ls.insert(ls.begin() + pos, people[i]);不可以，因為list不連續
            while(pos--){//尋找插入位置
                it++;
            }
            
            ls.insert(it, people[i]);
        }
        vector<vector<int>> res;
        for(auto ch : ls){
            res.push_back(ch);
        }
        return res;
    }
};

?最少數量的箭引爆?球

用最少數量的箭引爆氣球

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

一支弓箭可以沿著 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 {
    static bool cmp(vector<int>& p1, vector<int>& p2){
        return p1[0] < p2[0];
    }
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        if(points.size() == 0){
            return 0;
        }
        sort(points.begin(), points.end(), cmp);
        //有氣球，一定需要一根針
        int count = 1;
        for(int i =1; i<points.size(); i++){
            if(points[i][0] > points[i-1][1]){
                //不在重疊區間里，需要加一根針
                count++;
            }
            else{
                //在重疊區間里
                //找最小重疊區間結束值
                points[i][1] = min(points[i][1], points[i-1][1]);//下一次回圈就會是points[i][1] 
            }
        }

        return count;
        
    }
};

?重疊區間

無重疊區間

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

注意:

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

輸入: [ [1,2], [2,3], [3,4], [1,3] ]

輸出: 1

解釋: 移除 [1,3] 后，剩下的區間沒有重疊，

和上題思想差不多，

貪心思想：

區域最優：計算出每個重復區間的個數減1的和，

全域最優：需要移除區間個數，

怎么計算重復區間個數？

首先，按照左邊界從小到大排序，

其次，找重復區間個數，記錄重復區間的最小右邊界，當當前區間左邊界小于右邊界時，重復區間數加1，

class Solution {
    static bool cmp(vector<int>& p1, vector<int>& p2){
        return p1[0] < p2[0];
    }
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        //找出 重疊的區間個數
        
        sort(intervals.begin(), intervals.end(), cmp);
        int count = 0;//記錄重復區間個數
        for(int i = 1; i < intervals.size(); i++){
            //每個重復區間個數都會減1，第一個沒算進去
            if(intervals[i][0] < intervals[i - 1][1]){
                //重復
                count++;
                //記錄區間最小值
                intervals[i][1] = min(intervals[i][1], intervals[i-1][1]);
            }
        }
        return count;

    }
};

借鑒：「代碼隨想錄」貪?演算法專題精講