LeetCode link

Intuition

  • The input is already sorted, so what we do is to find the range of the insert.
  • Iterate the input, if current.end < new.start, just add it to the result.
  • Record the start which is the smaller one between new and current.
  • Continue iterate, when the current.start > end, we find the end edge of the insert position. Add a interval from start to end, and add the rest intervals.

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        List<Interval> result = new ArrayList<>();
        int start = newInterval.start;
        int end = newInterval.end;
        for (int i = 0; i < intervals.size(); i++) {
            Interval interval = intervals.get(i);
            if (interval.end < newInterval.start) {
                result.add(interval);
                continue;
            }
            start = Math.min(interval.start, start);
            if (interval.start > end) {
                result.add(new Interval(start, end));
                for (int j = i; j < intervals.size(); j++) {
                    result.add(intervals.get(j));
                }
                return result;
            }
            end = Math.max(end, interval.end);
        }
        result.add(new Interval(start, end));
        return result;
    }
}