[LeetCode]57.Insert Interval

本文主要是介绍[LeetCode]57.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].

思路

跟[LeetCode]56.Merge Intervals思路差不多。

代码

/*---------------------------------------------------------
*   日期：2015-04-22
*   作者：SJF0115
*   题目: 57.Insert Interval
*   网址：https://leetcode.com/problems/insert-interval/
*   结果：AC
*   来源：LeetCode
*   博客：
------------------------------------------------------------*/
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;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> result;result.push_back(newInterval);int size = intervals.size();if(size <= 0){return result;}//if// 插入for(int i = 0;i < size;++i){Interval one = result.back();Interval two = intervals[i];// [1,3] [5,6]// 插入倒数第二位if(two.end < one.start){Interval tmp = result.back();result.pop_back();result.push_back(two);result.push_back(tmp);}//if// 插入最后一位else if(two.start > one.end){result.push_back(two);}//else// 需合并else{int start = min(one.start,two.start);int end = max(one.end,two.end);Interval tmp(start,end);result.pop_back();result.push_back(tmp);}//else}//forreturn result;}
};int main(){Solution solution;Interval in1(1,2);Interval in2(3,5);Interval in3(6,7);Interval in4(8,10);Interval in5(12,16);vector<Interval> vec;vec.push_back(in1);vec.push_back(in2);vec.push_back(in3);vec.push_back(in4);vec.push_back(in5);Interval newInterval(4,9);// 合并vector<Interval> v = solution.insert(vec,newInterval);// 输出for(int i = 0;i < v.size();i++){Interval in = v[i];cout<<"["<<in.start<<","<<in.end<<"]"<<endl;}//forreturn 0;
}