Comment on page

# 57.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:
Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
Example 2:
Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].
NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

## 代码

### Approach #1 Greedy

class Solution {
public int[][] insert(int[][] intervals, int[] newInterval) {
// init data
int newStart = newInterval[0], newEnd = newInterval[1];
int idx = 0, n = intervals.length;
// 1. add all intervals starting before newInterval
while (idx < n && newStart > intervals[idx][0])
int[] interval = new int[2];
// if there is no overlap, just add the interval
if (output.isEmpty() || output.getLast()[1] < newStart)
// if there is an overlap, merge with the last interval
else {
interval = output.removeLast();
interval[1] = Math.max(interval[1], newEnd);
}
// 3. add next intervals, merge with newInterval if needed
while (idx < n) {
interval = intervals[idx++];
int start = interval[0], end = interval[1];
// if there is no overlap, just add an interval
if (output.getLast()[1] < start) {