首页 > 代码库 > 【LeetCode】Insert Interval

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

此题主要考虑到各种边界条件

可以用一些小的例子累得出循环的条件,注意将删除节点后应将i--

public class Solution {
    public ArrayList<Interval> insert(ArrayList<Interval> intervals,
            Interval newInterval) {
        if (intervals.isEmpty()) {
            intervals.add(newInterval);
            return intervals;
        }

        Interval pre = newInterval;
        for(int i=0;i<intervals.size();i++){
            int start = pre.start;
            int end = pre.end;
            Interval temp = intervals.get(i);
            
            if (temp.start > end) {
                intervals.add(i, pre);
                return intervals;
            } else if (temp.start == end) {
                temp.start = start;
                return intervals;
            } else {
                if (start <= temp.start && end <= temp.end) {
                    temp.start = start;
                    return intervals;
                } else if (start <= temp.start && end > temp.end) {
                    intervals.remove(temp);
                    i--;
                    continue;
                } else if (start > temp.start && end < temp.end) {
                    return intervals;
                } else if (start > temp.start &&start<temp.end&& end >=temp.end) {
                    pre.start = temp.start;
                    pre.end = end;
                    intervals.remove(temp);
                    i--;
                    continue;
                } else if (start > temp.end) {
                    pre.start = start;
                    pre.end = end;
                    continue;
                } else if (start == temp.end) {
                    pre.start = temp.start;
                    pre.end = end;
                    intervals.remove(temp);
                    i--;
                    continue;
                }
            }
        }
        intervals.add(pre);
        return intervals;

    }
}