-
Notifications
You must be signed in to change notification settings - Fork 3
/
_57_InsertInterval.java
55 lines (46 loc) · 1.56 KB
/
_57_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
package io.github.tahanima.leetcode;
/**
* @author tahanima
*/
public class _57_InsertInterval {
public boolean isOverlapping(int s0, int e0, int s1, int e1) {
if (s0 <= s1 && e0 >= e1) {
return true;
} else if (s0 >= s1 && e0 <= e1) {
return true;
} else if (e0 >= s1 && e0 <= e1) {
return true;
} else return s0 >= s1 && s0 <= e1;
}
public int[][] insert(int[][] intervals, int[] newInterval) {
int[] tempInterval = new int[100005];
int minStart = newInterval[0];
int maxStart = newInterval[0];
int size = 0;
for (int i = 0; i < 100005; i++) {
tempInterval[i] = -1;
}
for (int[] interval : intervals) {
minStart = Math.min(minStart, interval[0]);
maxStart = Math.max(maxStart, interval[0]);
if (isOverlapping(interval[0], interval[1], newInterval[0], newInterval[1])) {
newInterval[0] = Math.min(interval[0], newInterval[0]);
newInterval[1] = Math.max(interval[1], newInterval[1]);
} else {
tempInterval[interval[0]] = interval[1];
size++;
}
}
tempInterval[newInterval[0]] = newInterval[1];
size++;
int[][] answer = new int[size][2];
int j = 0;
for (int i = minStart; i <= maxStart; i++) {
if (tempInterval[i] >= 0) {
answer[j][0] = i;
answer[j++][1] = tempInterval[i];
}
}
return answer;
}
}