描述

Given a non-overlapping interval list which is sorted by start point.

Insert a new interval into it, make sure the list is still in order and non-overlapping (merge intervals if necessary).

样例

Insert (2, 5) into [(1,2), (5,9)], we get [(1,9)].

Insert (3, 4) into [(1,2), (5,9)], we get [(1,2), (3,4), (5,9)].

public class Solution {
    /**
     * @param intervals: Sorted interval list.
     * @param newInterval: new interval.
     * @return: A new interval list.
     */
    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        // write your code here
        
        // 1 find insert point and do insert
        // 2 merge if needed
        int insertPoint = -1;
        int low = 0, high = intervals.size()-1;
        while(low <= high) {
            int mid = (low + high) / 2;
            int midVal = intervals.get(mid).start;
            if (midVal == newInterval.start) {
                //find
                low = mid;
                break;
            } else if (midVal < newInterval.start) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        
        intervals.add(low, newInterval);
        System.out.println("low"+low);
        System.out.println("intervals.size"+intervals.size());
        int idx = low;
        if (idx - 1 >= 0 && intervals.get(idx-1).end >= intervals.get(idx).start){
            //last one
            intervals.get(idx-1).end = Math.max(intervals.get(idx-1).end,intervals.get(idx).end);
            intervals.remove(idx);
            idx--;
        }
        while((idx < intervals.size() - 1) && intervals.get(idx).end >= intervals.get(idx+1).start) {
            intervals.get(idx).end = Math.max(intervals.get(idx+1).end,intervals.get(idx).end);
            intervals.remove(idx+1);
        }
        return intervals;
    }
}

/**
 * Definition of Interval:
 * public classs Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this.start = start;
 *         this.end = end;
 *     }
 * }
 */

public class Solution {
    /**
     * @param intervals: Sorted interval list.
     * @param newInterval: new interval.
     * @return: A new interval list.
     */
    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        // write your code here
        
        List<Interval> res = new ArrayList<>();
        
        int index = 0;
        while(index < intervals.size()){
            if(newInterval.start > intervals.get(index).start){
                index++;
            }else{
                break;
            }
        }
        
        intervals.add(index,newInterval);
        
        Interval temp = null;
        for(Interval item : intervals){
            if(temp == null || temp.end < item.start){
                res.add(item);
                temp = item;
            }else {
                temp.end = Math.max(temp.end,item.end);
            }
        } 
        return res;
    }
    
}