57. Insert Interval

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

/** * Definition for an interval. * public class Interval { * int start; * int end; * Interval() { start = 0; end = 0; } * Interval(int s, int e) { start = s; end = e; } * } */class Solution { public List insert(List intervals, Interval newInterval) { List list = new ArrayList(); //边界情况 if(intervals.size() == 0){ list.add(newInterval); return list; } //循环判断 for(int i = 0; i < intervals.size();i++){ //如果新的区间结束值小于开始值，则直接插入前面，后面依次插入即可 if(newInterval.end < intervals.get(i).start){ list.add(newInterval); for(int j = i; j < intervals.size(); j++){ list.add(intervals.get(j)); } break; } //新的区间开始点大于结束点，则当前点直接添加结果集 else if(newInterval.start > intervals.get(i).end){ list.add(intervals.get(i)); } //需要合并的情况 else{ //合并区间 newInterval.start = Math.min(newInterval.start, intervals.get(i).start); newInterval.end = Math.max(newInterval.end, intervals.get(i).end); } if(i == intervals.size() - 1){//如果是最后一个数据。也添加结果集中 list.add(newInterval); } } return list; }}

class Solution { public int[][] insert(int[][] intervals, int[] newInterval) { List ans = new ArrayList<>(); if (newInterval == null) return intervals; if (intervals != null) { int i; boolean added = false; for (i = 0; i < intervals.length; i++) { if (added) ans.add(intervals[i]); else if (intervals[i][0] > newInterval[1]) { ans.add(newInterval); ans.add(intervals[i]); added = true; } else if (intervals[i][1] < newInterval[0]) ans.add(intervals[i]); else break; } if (i < intervals.length) /* means an overlap was found and the loop above broke out */{ int start = Math.min(intervals[i][0], newInterval[0]); int end = Math.max(intervals[i][1], newInterval[1]); for (i = i + 1; i < intervals.length; i++) { if (intervals[i][0] > end) { ans.add(new int[] {start, end}); break; } else end = Math.max(intervals[i][1], end); } if (i >= intervals.length) // means the end of overlapping region was not found since // the loop above never broke out ans.add(new int[] {start, end}); else for (; i < intervals.length; i++) ans.add(intervals[i]); } else if (!added) ans.add(newInterval); } else ans.add(newInterval); return ans.toArray(new int[ans.size()][2]); }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。