首页 > 代码库 > Insert Intervals
Insert Intervals
Given a non-overlapping interval list which is sorted by start point.
Insert a new interval into it, make sure the list is still in order and non-overlapping (merge intervals if necessary).
Example
Insert [2, 5] into [[1,2], [5,9]], we get [[1,9]].
Insert [3, 4] into [[1,2], [5,9]], we get [[1,2], [3,4], [5,9]].
Analyse: There are three possibilities for the newInterval and currentInterval: newInterval.end < currentInterval.start, newInterval.start > currentInterval.end, and newInterval and currentInterval intersects.
Runtime: 24ms
1 /** 2 * Definition of Interval: 3 * class Interval { 4 * public: 5 * int start, end; 6 * Interval(int start, int end) { 7 * this->start = start; 8 * this->end = end; 9 * }10 * }11 */12 class Solution {13 public:14 /**15 * Insert newInterval into intervals.16 * @param intervals: Sorted interval list.17 * @param newInterval: new interval.18 * @return: A new interval list.19 */20 vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {21 // write your code here22 vector<Interval> result;23 Interval pre = newInterval;24 for (int i = 0; i < intervals.size(); i++) {25 if (pre.end < intervals[i].start) {26 result.push_back(pre);27 pre = intervals[i];28 }29 else if (pre.start > intervals[i].end) {30 result.push_back(intervals[i]);31 }32 else {33 pre.start = min(pre.start, intervals[i].start);34 pre.end = max(pre.end, intervals[i].end);35 }36 }37 result.push_back(pre);38 return result;39 }40 };
Insert Intervals
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。