?LeetCode刷題實(shí)戰(zhàn)56：合并區(qū)間
算法的重要性，我就不多說了吧，想去大廠，就必須要經(jīng)過基礎(chǔ)知識(shí)和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個(gè)公眾號(hào)后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選 ！
今天和大家聊的問題叫做?合并區(qū)間，我們先來看題面：
https://leetcode-cn.com/problems/merge-intervals/
Given a collection of intervals, merge all overlapping intervals.
題意
樣例
示例 1:
輸入: intervals = [[1,3],[2,6],[8,10],[15,18]]
輸出: [[1,6],[8,10],[15,18]]
解釋: 區(qū)間 [1,3] 和 [2,6] 重疊, 將它們合并為 [1,6].
示例?2:
輸入: intervals = [[1,4],[4,5]]
輸出: [[1,5]]
解釋: 區(qū)間 [1,4] 和 [4,5] 可被視為重疊區(qū)間。
解題
class?Solution?{
public:
??static?bool?myCompare(Interval one, Interval two){
????//以start為主次序遞增
????if?(one.start == two.start){//當(dāng)start相等的時(shí)候，才進(jìn)行比較end
??????return?one.end < two.start;
????}
????else?{//否則直接比較start的大小關(guān)系
??????return?one.start < two.start;
????}
??}
??vectormerge(vector & intervals) {
????sort(intervals.begin(), intervals.end(), myCompare);//按照自定義順序進(jìn)行排序
????for?(int?i = 0; i < intervals.size(); ++i){//動(dòng)態(tài)掃描
??????int?begin = intervals[i].start;//基準(zhǔn)begin
??????int?end = intervals[i].end;//基準(zhǔn)end
??????//因?yàn)榕判虻臅r(shí)候就保證了start為主次序遞增，只要下一個(gè)的start小于上一個(gè)的end，就證明可以進(jìn)行合并
??????while?(i + 1?< intervals.size() && intervals[i + 1].start <= end){//如果能進(jìn)行合并
????????end = max(intervals[i + 1].end, end);//更新
????????intervals.erase(intervals.begin() + i + 1);
??????}
??????intervals[i].end = end;//更新i的end
????}
????return?intervals;
??}
};
上期推文：