首页 > 代码库 > 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].
Solution:
1 /** 2 * Definition for an interval. 3 * public class Interval { 4 * int start; 5 * int end; 6 * Interval() { start = 0; end = 0; } 7 * Interval(int s, int e) { start = s; end = e; } 8 * } 9 */10 public class Solution {11 public List<Interval> insert(List<Interval> intervals, Interval newInterval) {12 List<Interval> newList = new ArrayList<Interval>();13 14 if (intervals.size()==0&&newInterval==null) return newList;15 16 if (intervals.size()==0){17 newList.add(newInterval);18 return newList;19 }20 21 if (newInterval==null)22 return intervals;23 24 int index = 0;25 int st = newInterval.start;26 int et = newInterval.end;27 for (int i=0;i<intervals.size();i++){28 Interval temp = intervals.get(i);29 if (temp.end<st){30 newList.add(temp);31 index++;32 continue;33 } else 34 break;35 }36 37 //At the end of the intervals.38 if (index==intervals.size()){39 intervals.add(newInterval);40 return intervals;41 }42 43 Interval res = new Interval();44 res.end = -1;45 Interval temp = intervals.get(index);46 if (temp.start>st)47 res.start = st;48 else49 res.start = temp.start;50 51 //This is important.52 if (temp.end<et)53 index++;54 55 while (index<intervals.size()){56 temp = intervals.get(index);57 if (temp.end<et){58 //newList.add(temp);59 index++;60 continue;61 } 62 63 if (temp.end==et){64 res.end = et;65 index++;66 break;67 }68 69 if (temp.start<=et){70 res.end = temp.end;71 index++;72 break;73 }74 75 if (temp.start>et){76 res.end = et;77 break;78 } 79 }80 81 if (res.end==-1){82 res.end = et;83 newList.add(res);84 return newList;85 }86 87 newList.add(res);88 89 while (index<intervals.size()){90 temp = intervals.get(index);91 newList.add(temp);92 index++;93 }94 95 96 return newList;97 }98 }
This problem is not hard, but we need to consider every situation of start and end of the inserted interval.
Leetcode-Insert Interval
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。