LeetCode - Insert Interval
Problem description
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:
1
2
Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
Example 2:
1
2
3
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].
Analysis
Basically, we can iterate all element and merge them with inserted one.
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
26
27
public int[][] insert(int[][] intervals, int[] newInterval) {
List<int[]> res = new ArrayList<>();
int inserted = 0;
for(int[] interval: intervals){
if (interval[1] < newInterval[0]){
res.add(interval);
}
else if (interval[0] > newInterval[1]){
if (inserted == 0){
res.add(newInterval);
inserted = 1;
}
res.add(interval);
}
else {
newInterval[0] = Math.min(newInterval[0], interval[0]);
newInterval[1] = Math.max(newInterval[1], interval[1]);
}
}
if (intervals.length == 0 || inserted== 0){
res.add(newInterval);
}
return res.toArray(new int[res.size()][2]);
}
What to improve
- consider the edge case when no bigger interval or original array is empty.