首页 > 代码库 > LeetCode--Merge Intervals
LeetCode--Merge Intervals
Given a collection of intervals, merge all overlapping intervals.
For example,
Given [1,3],[2,6],[8,10],[15,18]
,
return [1,6],[8,10],[15,18]
.
/** * Definition for an interval. * struct Interval { * int start; * int end; * Interval() : start(0), end(0) {} * Interval(int s, int e) : start(s), end(e) {} * }; */ class Solution { public: vector<Interval> merge(vector<Interval> &intervals) { vector<Interval> res; vector<Interval>& in = intervals; int n = in.size(); if(n == 0) return res; if(n == 1) return in; heap_sort(in); Interval temp = in[0]; for(int i=1; i<n; i++) { if(temp.end < in[i].start) { res.push_back(temp); temp = in[i]; } else { int start = temp.start<in[i].start? temp.start:in[i].start; int end = temp.end>in[i].end? temp.end:in[i].end; temp.start = start; temp.end = end; } } res.push_back(temp); return res; } void swap(vector<Interval>& in, int i, int j) { int s = in[i].start; int e = in[i].end; in[i].start = in[j].start; in[i].end = in[j].end; in[j].start = s; in[j].end = e; } void sink(vector<Interval>& in, int loc, int end) { while(loc<end) { int k =2*loc+1; if(k>end) return; if(k<end && in[k].start<in[k+1].start) k++; if(in[loc].start>in[k].start) return; swap(in,loc,k); loc = k; } } void heap_sort(vector<Interval>& in) { int n = in.size()-1; for(int i=(n-1)/2; i>=0; i--) sink(in,i,n); while(n>0) { swap(in,0,n); n--; sink(in,0,n); } } };
LeetCode--Merge Intervals
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。