首页 > 代码库 > LeetCode--Insert Interval
LeetCode--Insert Interval
Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
You may assume that the intervals were initially sorted according to their start times.
Example 1:
Given intervals [1,3],[6,9]
, insert and merge [2,5]
in as [1,5],[6,9]
.
Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16]
, insert and merge [4,9]
in as [1,2],[3,10],[12,16]
.
This is because the new interval [4,9]
overlaps with [3,5],[6,7],[8,10]
.
/** * 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> insert(vector<Interval> &intervals, Interval newInterval) { vector<Interval>& in = intervals; heap_sort(in); int n = in.size(); vector<Interval> res; bool flag = false; for(int i=0; i<n; i++) { if(in[i].start > newInterval.start && flag==false) { res.push_back(newInterval); flag = true; } res.push_back(in[i]); } if(!flag) res.push_back(newInterval); return merge(res); } 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; 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--Insert Interval
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。