首页 > 代码库 > LeetCode: Insert Interval [056]
LeetCode: Insert Interval [056]
【题目】
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]
.
【题意】
给定一个不重叠区间集合,集合按区间的起始值已经排好序,插入一个区间,如果插入的区间与某些区间重叠,则合并
【思路】
依次扫描集合中的各个区间,和待插入集合比较,确定待插入集合的位置或新合并集合的起始值。
关键在于比较:集合中每个区间interval[start, end]和insertInterval[start, end]有以下几种可能的位置关系
1. interval在insertInterval的左边,即interval.end<insertInterval.start
2. Interval的右边界在insertInterval区间内,而左边界还在InsertInterval区间外,即Interval.start<insertInterval.start && Interval.end>=insertInterval.start && Interval.end<=insertInterval.end;
3. Interval区间覆盖了insertInterval区间,即Interval.start<InsertInterval.start&&Interval.end>InsertInterval.end
4. Interval区间被InsertInterval区间覆盖,即interval.start>=insertInterval.start&&interval.end<InsertInterval.end
5. Interval左边界在InsertInterval区间内,而右边界还在InsertInterval区间外,即Interval.start>=InsertInterval.start && Interval.end<=InsertInterval.end && interval.end>InsertInterval.end
6. Interval在InsertInterval的右边,即Interval.start>InsertInterval.end
【代码】
/** * 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>result; int size=intervals.size(); bool hasInserted=false; //是否已经插入 for(int i=0; i<size; i++){ if(hasInserted){ //如果新区间已经插入,则区间集合中的后续集合直接添加到result集合中即可 result.push_back(intervals[i]); continue; } if(intervals[i].start<newInterval.start){ if(intervals[i].end<newInterval.start){ //在新区间的左侧 result.push_back(intervals[i]); } else if(intervals[i].end<=newInterval.end){ //右边界新区间内,也即存在重合,更新新区间的左边界 newInterval.start=intervals[i].start; } else{ //当前区间覆盖了新区间 result.push_back(intervals[i]); hasInserted=true; } } else{ if(intervals[i].start>newInterval.end){ //在新区间的右边,插入新区间,及当前区间 【注意,这种情况下需要插入两个区间】 result.push_back(newInterval); result.push_back(intervals[i]); hasInserted=true; } else if(intervals[i].end<=newInterval.end){ //当前区间被新区间包含 continue; } else{ //左边界在新区间内,也即存在重合,更新新区间的右边界 newInterval.end=intervals[i].end; } } } if(!hasInserted){ result.push_back(newInterval); } return result; } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。