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.

答案

class Solution {
public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        // First, find what intervals overlap with newInterval
        List<Integer> overlaps = new ArrayList<>();
        List<Interval> ret = new ArrayList<>();
        int insert_pos = 0;
        for(int i = 0; i < intervals.size(); i++) {
            Interval i1 = intervals.get(i), i2 = newInterval;
            if(Math.max(i1.start, i2.start) <= Math.min(i1.end, i2.end)) {
                overlaps.add(i);
            }
            if(i1.end < i2.start) insert_pos = i + 1;
        }

        // If there is no overlap, simply insert
        if(overlaps.size() == 0) {
            intervals.add(insert_pos, newInterval);
            return intervals;
        }
        // If there is overlap, merge them into a new interval by taking [min, max] of all involved intervals
        int min = Math.min(newInterval.start, intervals.get(overlaps.get(0)).start);
        int max = Math.max(newInterval.end, intervals.get(overlaps.get(overlaps.size() - 1)).end);
        Interval merged = new Interval(min, max);

        for(int i = 0; i < intervals.size(); i++) {
            if(!overlaps.contains(i)) {
                ret.add(intervals.get(i));
            }
            else {
                if(i == overlaps.get(0)) ret.add(merged);
            }
        }
        return ret;
    }
}