IT工程師數位筆記本

Leetcode 435題目解答：先對區間進行排序，然后遍歷所有區間，盡量去掉長區間，則保留的區間數目一定最多。

bool cmp(Interval a, Interval b) {    return a.start < b.start; }class Solution {public:    int eraseOverlapIntervals(vector& intervals) {        sort(intervals.begin(), intervals.end(), cmp);        int res = 0, pre = 0; //res記錄保留區間的個數，pre記錄每次需要判斷是否重疊的起始區間        for (int i = 1; i < intervals.size(); i++) {            if (intervals[i].start < intervals[pre].end) {                res++; //當前區間起始值小于pre區間的末尾保留上一個區間                if (intervals[i].end < intervals[pre].end) pre = i;                //這個的意思是從集合中去掉的元素是pre（因為pre太長）            }            else pre = i; //區間i和區間pre已經不重疊，需要判斷重疊的起始區間pre后移        }        return res;    }};

看文倉www.kanwencang.com網友整理上傳,為您提供最全的知識大全,期待您的分享，轉載請注明出處。
歡迎轉載：http://www.kanwencang.com/bangong/20170116/88819.html

文章列表

不含病毒。www.avast.com