LeetCode每日一题：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].

问题分析

这道题的意思是给出一个区间，和原区间进行比较后若重合则覆盖，最后给出覆盖后的新区间。

1. 遍历原来的List
2. 如果新区间的end < 当前区间的start，不用找下去了，把新区间插入到当前区间的前面，然后返回。
3. 如果当前区间的end小于新区间的start，继续遍历找下一个区间。
4. 如果当前区间和新区间发生重合，则start取两者最小的start，end取两者最大的end，生成一个新的区间。
5. 继续遍历。

代码实现

public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
        if (intervals == null || newInterval == null) return intervals;
        if (intervals.size() == 0) {
            intervals.add(newInterval);
            return intervals;
        }
        ListIterator<Interval> iterator = intervals.listIterator();
        while (iterator.hasNext()) {
            Interval tmpInterval = iterator.next();
            if (newInterval.end < tmpInterval.start) {
                iterator.previous();
                iterator.add(newInterval);
                return intervals;
            } else {
                if (tmpInterval.end < newInterval.start) continue;
                else {
                    newInterval.start = Math.min(tmpInterval.start, newInterval.start);
                    newInterval.end = Math.max(tmpInterval.end, newInterval.end);
                    iterator.remove();
                }
            }
        }
        intervals.add(newInterval);
        return intervals;
    }