Leetcode/各大家 -- 57. Insert Interval(Array Sort)

57. Insert Interval(Array)
hard
https://leetcode.com/problems/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].

LinkedIn Google Facebook

思路： Merge when curInterval.end >  newInterval.start && curInterval.start <= newInterval.end
            Merge the newInterval with old one into newInterval  by keep the min as start, max as end.
            Do it in place by remove the old ones that are merged, watch index(i), no need to modify.
            And finally insert interval to result.
Complexity: O(N)time, O(1)space

/**
 * 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; }
 * }
 */
public class Solution {
    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        int i = 0;
        // add all the intervals ending before newInterval starts
        while(i < intervals.size() && intervals.get(i).end < newInterval.start)
            i++;
        // merge all overlapping intervals to one considering newInterval
        while(i < intervals.size() && intervals.get(i).start <= newInterval.end){
            newInterval = new Interval( 
                Math.min(intervals.get(i).start, newInterval.start),
                Math.max(intervals.get(i).end, newInterval.end));
            intervals.remove(i);//no modify i since removal(i), so next loop i will get next element in list
        }
        intervals.add(i, newInterval);
        return intervals;
    }
}