Poison

57. Insert Interval

Linked List
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
class Solution {
private static class Entry {
private int[] interval;
private Entry prev;
private Entry next;

public Entry(int[] interval, Entry prev) {
this.interval = interval;
this.prev = prev;
}
}

public int[][] insert(int[][] intervals, int[] newInterval) {
// 首先判断是否与已有区间重叠,如果不重叠,则插入至指定位置,如果重叠则需要合并区间

Entry dummyHead = new Entry(null, null);
Entry current = dummyHead;

Entry insertEntry = dummyHead;
Entry targetEntry = null;
for (int[] interval : intervals) {
current.next = new Entry(interval, current);
current = current.next;

if (interval[0] < newInterval[0]) {
insertEntry = current;
}
if (targetEntry == null && hasCommonInterval(interval, newInterval)) {
targetEntry = current;
}
}

if (targetEntry == null) {
// 无重复区间,将区间插入即可
Entry next = insertEntry.next;
insertEntry.next = new Entry(newInterval, insertEntry);
insertEntry.next.next = next;
if (next != null) {
next.prev = insertEntry.next;
}
} else {
// 存在重复区间,插入并合并区间
targetEntry.interval = mergeInterval(targetEntry.interval, newInterval);
// 合并区间后,当前区间左侧和右侧可能与左右区间存在交集,则需要尝试不停向左侧或右侧合并
while (targetEntry.prev != null && targetEntry.prev.interval != null && hasCommonInterval(targetEntry.prev.interval, targetEntry.interval)) {
targetEntry.interval = mergeInterval(targetEntry.prev.interval, targetEntry.interval);
Entry prevOfPrev = targetEntry.prev.prev;
if (prevOfPrev != null) {
prevOfPrev.next = targetEntry;
}
targetEntry.prev = prevOfPrev;
}
while (targetEntry.next != null && targetEntry.next.interval != null && hasCommonInterval(targetEntry.next.interval, targetEntry.interval)) {
targetEntry.interval = mergeInterval(targetEntry.next.interval, targetEntry.interval);
Entry nextOfNext = targetEntry.next.next;
if (nextOfNext != null) {
nextOfNext.prev = targetEntry;
}
targetEntry.next = nextOfNext;
}
}

List<int[]> intervalList = new LinkedList<>();
current = dummyHead.next;
while (current != null) {
intervalList.add(current.interval);
current = current.next;
}

return intervalList.toArray(new int[0][]);
}

private int[] mergeInterval(int[] a, int[] b) {
return new int[]{Math.min(a[0], b[0]), Math.max(a[1], b[1])};
}

private boolean hasCommonInterval(int[] a, int[] b) {
if (a[0] > b[0]) {
return hasCommonInterval(b, a);
}

return a[1] >= b[0];
}
}
Iterate
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
class Solution {
public int[][] insert(int[][] intervals, int[] newInterval) {
boolean inserted = false;
int start = newInterval[0], end = newInterval[1];
List<int[]> list = new ArrayList<>(intervals.length + 1);
for (int[] interval : intervals) {
if (interval[1] < newInterval[0]) {
// 当前区间位于新区间左侧
list.add(interval);
} else if (interval[0] > newInterval[1]) {
// 当前区间位于新区间右侧
if (!inserted) {
// 遇到了新的不交集的区间,如果之前存在交集的区间,则在此处添加
list.add(new int[]{start, end});
inserted = true;
}
list.add(interval);
} else {
// 存在交集
start = Math.min(start, interval[0]);
end = Math.max(end, interval[1]);
}
}

// 处理交集区间全部位于数组尾部的情况
if (!inserted) {
list.add(new int[]{start, end});
}

int[][] array = new int[list.size()][];
for (int i = 0; i < list.size(); i++) {
array[i] = list.get(i);
}
return array;
}
}
Reference

57. Insert Interval