-
Notifications
You must be signed in to change notification settings - Fork 2
/
InsertInterval.java
85 lines (75 loc) · 2.41 KB
/
InsertInterval.java
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
package Leetcode;
import java.util.ArrayList;
import java.util.List;
/**
* @author kalpak
*
* 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]]
*
*
* Constraints:
*
* 0 <= intervals.length <= 104
* intervals[i].length == 2
* 0 <= intervals[i][0] <= intervals[i][1] <= 105
* intervals is sorted by intervals[i][0] in ascending order.
* newInterval.length == 2
* 0 <= newInterval[0] <= newInterval[1] <= 105
*/
public class InsertInterval {
public static int[][] insert(int[][] intervals, int[] newInterval) {
List<int[]> result = new ArrayList<>();
for(int[] i : intervals) {
if(newInterval == null || i[1] < newInterval[0]) // current interval is on the left of the new interval and no overlap
result.add(i);
else if (i[0] > newInterval[1]) { // current interval is on the right of the new interval and no overlap
result.add(newInterval);
result.add(i);
newInterval = null;
} else {
// overlap
newInterval[0] = Math.min(newInterval[0], i[0]);
newInterval[1] = Math.max(newInterval[1], i[1]);
}
}
if(newInterval != null)
result.add(newInterval);
return result.toArray(new int[result.size()][]);
}
public static void printResult(int[][] result) {
for(int[] i : result) {
System.out.print("["+i[0]+" "+i[1]+"],");
}
System.out.println();
}
public static void main(String[] args) {
int[][] intervals = new int[][]{{2, 5}, {6, 7}, {8, 9}};
int[] newInterval = new int[]{0, 1};
printResult(insert(intervals, newInterval));
}
}