LeetCode

题目：

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

思路：

先找到newInterval的插入位置，然后合并

package interval;

import java.util.ArrayList;
import java.util.List;

public class InsertInterval {

    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        int n = 0;
        if (intervals == null) return new ArrayList<Interval>();
        if ((n = intervals.size()) == 0) {
            intervals.add(newInterval);
            return intervals;
        }
        
        int cur = 0;
        for (; cur < n; ++cur) {
            if (intervals.get(cur).start >= newInterval.start) {
                break;
            }
        }
        
        intervals.add(cur, newInterval);
        int prev = cur - 1;
        // We added one element, so in for loop, i < n + 1
        for (int i = cur; i < n + 1; ++i) {
            if (i >= 1 && overlapped(intervals.get(prev), intervals.get(i))) {
                intervals.set(prev, new Interval(intervals.get(prev).start, 
                        intervals.get(prev).end > intervals.get(i).end ? intervals.get(prev).end : intervals.get(i).end));
            } else {
                intervals.set(++prev, intervals.get(i));
            }
        }    
        
        return intervals.subList(0, prev + 1);
    }
    
    private boolean overlapped(Interval a, Interval b) {
        return a.start <= b.start ? a.end >= b.start : overlapped(b, a);
    }
    
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        List<Interval> intervals = new ArrayList<Interval>();
        intervals.add(new Interval(1,2));
        intervals.add(new Interval(3,5));
        intervals.add(new Interval(6,7));
        intervals.add(new Interval(8,10));
        intervals.add(new Interval(12,16));
        
        Interval newInterval = new Interval(4,9);
        InsertInterval insertInterval = new InsertInterval();
        List<Interval> res = insertInterval.insert(intervals, newInterval);
        for (Interval i : res) {
            System.out.println("[" + i.start + ", " + i.end + "]");
        }
    }

}