Merge Intervals
Merging
+------+ +----------------+
| | | |
+---------------+ +-------------+ |
| | | | | | | |
+---+------+----+ +---+---------+------+
figure. 1 figure. 2
- figure. 1
An interval contains another interval, the merged one is the bigger one.
- figure. 2
An interval overlaps another interval, the merged one is smaller start and bigger end
function merge(i1. i2)
return { start = MIN(i1.start, i2.start), end = MAX(i1.end, i2.end) }
Merge using a stack [Loop invariant]
Assume that all intervals into a stack and all intervals are sorted by start.
The top two intervals in the stack are the smallest in start.
If the top two cant be merged into one, the smaller one must cant be merged with any other intervals. in another word, the smaller one can be put into final result set.
stack with sorted intervals
while stack is not empty
smallest = stack.pop()
secondary smallest = stack.pop()
if can merge (overlap or contain)
merged = merge(smallest, secondary smallest)
stack.push(merged)
else
put smallest into results
stack.push(secondary smallest)
Source code Read on Github
1 /**
2 * Definition for an interval.
3 * public class Interval {
4 * int start;
5 * int end;
6 * Interval() { start = 0; end = 0; }
7 * Interval(int s, int e) { start = s; end = e; }
8 * }
9 */
10 public class Solution {
11 public List<Interval> merge(List<Interval> intervals) {
12
13 ArrayList<Interval> rt = new ArrayList<Interval>();
14
15 Collections.sort(intervals, new Comparator<Interval>() {
16 public int compare(Interval o1, Interval o2) {
17 return o1.start - o2.start;
18 }
19 });
20
21 LinkedList<Interval> s = new LinkedList<Interval>(intervals);
22
23 while (s.size() > 1) {
24 Interval i1 = s.pop();
25 Interval i2 = s.pop();
26
27 if (i1.end >= i2.start) {
28 s.push(new Interval(i1.start, Math.max(i1.end, i2.end)));
29 } else {
30 s.push(i2);
31 rt.add(i1);
32 }
33 }
34
35 rt.addAll(s);
36
37 return rt;
38 }
39 }