看完本文，可以順便解決leetcode以下題目：

435.無重疊區(qū)間（中等）

一、通俗易懂的 貪心算法 |思想 (重復(fù)一次~~~)

貪心算法就是采用貪心的策略，保證每一次的操作都是局部最優(yōu)的，從而使得結(jié)果是全局最優(yōu)的。

比如，A、B、C、都很喜歡吃橘子，A可以吃5個(gè)、B可以吃3個(gè)、C可以吃1個(gè)；但是現(xiàn)在只有7個(gè)橘子，問最多幾個(gè)人可以吃飽；

我們選用的貪心策略就是，吃的少的人先吃，盡量先使用量少的人吃飽，所以在這里，B、C肯定是可以吃飽的；

在這里，又因?yàn)槿纸Y(jié)果是局部結(jié)果的簡(jiǎn)單求和，因此，局部最優(yōu)的策略同樣也是全局最優(yōu)的策略。

二、區(qū)間問題

435.無重疊區(qū)間(中等)

題目描述

給定一個(gè)區(qū)間的集合，找到需要移除區(qū)間的最小數(shù)量，使剩余區(qū)間互不重疊
來源：力扣（LeetCode）

輸入輸出樣例

輸入: [ [1,2], [2,3], [3,4], [1,3] ]
輸出: 1
解釋: 移除 [1,3] 后，剩下的區(qū)間沒有重疊。
來源：力扣（LeetCode）

題解

首先，我們能夠看出來，重疊的判斷條件是: 一號(hào)區(qū)間的區(qū)頭 < 二號(hào)區(qū)間的區(qū)尾。；所以區(qū)尾的元素越小，可以留下來的區(qū)間數(shù)目就越多，自然移除的區(qū)間數(shù)目就更少了；

所以此題的貪心策略是：不能重疊，優(yōu)先保留區(qū)尾的元素小的區(qū)間。

所以，我們第一步，應(yīng)該對(duì)于當(dāng)前的區(qū)間集合，做一個(gè)排序，按照各個(gè)區(qū)間區(qū)尾的值進(jìn)行增序排序；然后進(jìn)行判斷，保留下來不重疊的區(qū)間，同時(shí)對(duì)于去除區(qū)間的操作進(jìn)行計(jì)數(shù)；

class Solution { public:int eraseOverlapIntervals(vector<vector<int>>& intervals) {if (intervals.empty()) {return 0;}int n = intervals.size();// 首先是對(duì)當(dāng)前的集合 做區(qū)尾增序處理sort(intervals.begin(),intervals.end(),[](vector<int>a,vector<int> b){return a[1] < b[1];});int total = 0;int prev = intervals[0][1];for (int i = 1; i < n; ++i) {if (intervals[i][0] < prev) { // 下一個(gè)區(qū)頭比區(qū)尾小 說明和下一個(gè)重合了++ total;} else {prev = intervals[i][1]; // 繼續(xù)下一個(gè)}}return total;} };

總結(jié)

以上是生活随笔為你收集整理的通俗易懂：贪心算法（二）：区间问题 （力扣435无重叠区间）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。