-
Notifications
You must be signed in to change notification settings - Fork 2
Expand file tree
/
Copy pathInsertInterval.java
More file actions
117 lines (111 loc) · 4.82 KB
/
InsertInterval.java
File metadata and controls
117 lines (111 loc) · 4.82 KB
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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
/**
* Definition for an interval.
* public class Interval {
* int start;
* int end;
* Interval() { start = 0; end = 0; }
* Interval(int s, int e) { start = s; end = e; }
* }
*/
public class InsertInterval {
//O(n) time and O(n) space, non-inplace solution.
public List<Interval> insert0(List<Interval> intervals, Interval newInterval) {
List<Interval> result = new ArrayList<>();
int i = 0;
for (;i < intervals.size() && intervals.get(i).end < newInterval.start; result.add(intervals.get(i++)));
Interval mergedInterval = new Interval(newInterval.start, newInterval.end);
for(; i < intervals.size() && intervals.get(i).start <= mergedInterval.end; ++i) {
mergedInterval.start = Math.min(mergedInterval.start, intervals.get(i).start);
mergedInterval.end = Math.max(mergedInterval.end, intervals.get(i).end);
}
result.add(mergedInterval);
for(; i < intervals.size(); result.add(intervals.get(i++)));
return result;
}
//Same algorithm and performance as above, but use iterator instead of index to do iteration.
//This is better than above because if the list is linked list, list.get(i) could be very expensive.
public List<Interval> insert1(List<Interval> intervals, Interval newInterval) {
List<Interval> result = new ArrayList<>();
ListIterator<Interval> iter = intervals.listIterator();
Interval mergedInterval = new Interval(newInterval.start, newInterval.end);
boolean isInserted = false;
for (;iter.hasNext();) {
Interval curInterval = iter.next();
if (curInterval.end < newInterval.start) {
result.add(curInterval);
} else if (curInterval.start <= newInterval.end) {
mergedInterval.start = Math.min(mergedInterval.start, curInterval.start);
mergedInterval.end = Math.max(mergedInterval.end, curInterval.end);
} else {
if (!isInserted) {
result.add(mergedInterval);
isInserted = true;
}
result.add(curInterval);
}
}
if (!isInserted) {
result.add(mergedInterval);
}
return result;
}
//Better implementation using iterator.
//The helper function is important.
//result stores non-overlapping intervals sorted by their start times.
//The start time of newInterval is greater or equal to the last interval in result
private void addInterval(List<Interval> result, Interval newInterval) {
Interval lastInterval = (result.size() == 0) ? null : result.get(result.size() - 1);
if (lastInterval == null || lastInterval.end < newInterval.start) {
result.add(newInterval);
} else {
lastInterval.end = Math.max(lastInterval.end, newInterval.end);
}
}
public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
List<Interval> result = new ArrayList<>();
Iterator<Interval> iter = intervals.iterator();
boolean isInserted = false;
for(; iter.hasNext();) {
Interval curInterval = iter.next();
if (curInterval.start < newInterval.start) {
result.add(curInterval);
} else if (!isInserted) {
addInterval(result, newInterval);
addInterval(result, curInterval);
isInserted = true;
} else {
addInterval(result, curInterval);
}
}
if (!isInserted) {
addInterval(result, newInterval);
}
return result;
}
//In place solution. O(n^2) time and O(1) space. Same algorithm as above.
public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
ListIterator<Interval> iter = intervals.listIterator();
Interval mergedInterval = new Interval(newInterval.start, newInterval.end);
boolean isInserted = false;
for (;iter.hasNext();) {
Interval curInterval = iter.next();
if (curInterval.end >= newInterval.start) {
if (curInterval.start <= newInterval.end) {
mergedInterval.start = Math.min(mergedInterval.start, curInterval.start);
mergedInterval.end = Math.max(mergedInterval.end, curInterval.end);
iter.remove();
} else {
if (!isInserted) {
iter.previous();
iter.add(mergedInterval);
isInserted = true;
}
}
}
}
if (!isInserted) {
iter.add(mergedInterval);
}
return intervals;
}
}