問題
給定一組區間，找出沒有重疊區間最多的區間個數。

思路[谷歌高暢力扣刷題筆記]
貪心算法，貪心策略是優先保留結尾小且不相交的區間。
首先根據右邊界升序排序，然后依次比較左邊界和前面的右邊界：沒有重疊就是滿足條件的區間，有重疊就更新右邊界。

代碼

int eraseOverlapIntervals(vector<vector<int>>& intervals) {if(intervals.empty()) { // 沒有元素return 0;}int n = intervals.size();sort(intervals.begin(), intervals.end(), [](vector<int>& a, vector<int>& b) { // 根據右邊界升序排列return a[1] < b[1];});int cnt=0, prev=intervals[0][1]; // prev代表右邊界for(int i=1; i<n; i++) {if(intervals[i][0] < prev) { // 左邊界不在前一個的范圍內->沒有相交部分cnt++;} else { // 左邊界在前一個的范圍內->更新右邊界prev = intervals[i][1];}}return cnt;}

總結

以上是生活随笔為你收集整理的435-无重叠区间的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。