57. Insert Interval

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

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

Example 3:

Input: intervals = [], newInterval = [5,7]
Output: [[5,7]]

Example 4:

Input: intervals = [[1,5]], newInterval = [2,3]
Output: [[1,5]]

Example 5:

Input: intervals = [[1,5]], newInterval = [2,7]
Output: [[1,7]]

Code

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> list = new ArrayList<>();

        boolean added = false;

        for(int i = 0; i < intervals.length; i++){
            int[] inter = intervals[i];

            // 后开始的和先结束的
            // 判断有没有重叠
            int maxStart = Math.max(inter[0], newInterval[0]);
            int minEnd = Math.min(inter[1], newInterval[1]);

            if(maxStart <= minEnd) {
                newInterval[0] =  Math.min(inter[0], newInterval[0]);
                newInterval[1] = Math.max(inter[1], newInterval[1]);
            } else {
                if(inter[0] > newInterval[1] && added == false) {
                    list.add(newInterval);
                    added = true;
                }
                list.add(inter);
            }
        }

        if(added == false) {
            list.add(newInterval);
        }

        int[][] res = new int[list.size()][2];
        for(int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }

        return res;
    }
}