首页 > 代码库 > Insert Interval leetcode java

Insert Interval leetcode java

2024-07-14 09:21:39   225人阅读

题目：

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].

 

题解：

这道题不仅要insert newInterval同时还要保证能够merge。那么就分情况讨论。

遍历每一个已给出的interval，

当当前的interval的end小于newInterval的start时，说明新的区间在当前遍历到的区间的后面，并且没有重叠，所以res添加当前的interval；

当当前的interval的start大于newInterval的end时，说明新的区间比当前遍历到的区间要前面，并且也没有重叠，所以把newInterval添加到res里，并更新newInterval为当前的interval；

当当前的interval与newInterval有重叠时，merge interval并更新新的newInterval为merge后的。

 

代码如下：

 

 1     public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
 2         ArrayList<Interval> res = new ArrayList<Interval>();
 3             
 4         for(Interval each: intervals){
 5             if(each.end < newInterval.start){
 6                 res.add(each);
 7             }else if(each.start > newInterval.end){
 8                 res.add(newInterval);
 9                 newInterval = each;        
10             }else if(each.end >= newInterval.start || each.start <= newInterval.end){
11                 int nstart = Math.min(each.start, newInterval.start);
12                 int nend = Math.max(newInterval.end, each.end);
13                 newInterval = new Interval(nstart, nend);
14             }
15         }
16  
17         res.add(newInterval); 
18  
19         return res;
20     }

 Reference：//http://www.programcreek.com/2012/12/leetcode-insert-interval/

 


联系
我们