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].
public class Solution { public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) { int s = -1, e = -1; for(int i = 0 ; i < intervals.size() ; i++){ if(s == -1 && intervals.get(i).end >= newInterval.start)// start position s = i ; if(intervals.get(i).start <= newInterval.end) e = i; } if(s == -1){//insert in the end intervals.add(newInterval); return intervals; } if(e == -1){//insert in the start intervals.add(0,newInterval); return intervals; } int start = Math.min(intervals.get(s).start,newInterval.start); int end = Math.max(intervals.get(e).end, newInterval.end); intervals.subList(s,e+1).clear(); if(s<intervals.size()){//extra interval exsiting intervals.add(s, new Interval(start,end));// s is position } else{ intervals.add( new Interval(start,end)); } return intervals; } }
public class Solution { public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) { ArrayList<Interval> result = new ArrayList<Interval>(); for(Interval interval:intervals){ if(interval.start > newInterval.end){ result.add(newInterval); newInterval = interval; } else if(interval.end < newInterval.start){ result.add(interval); } else if(interval.end >= newInterval.start || interval.start <= newInterval.end){ newInterval = new Interval(Math.min(interval.start,newInterval.start),Math.max(interval.end,newInterval.end)); } } result.add(newInterval); return result; } }