-
Notifications
You must be signed in to change notification settings - Fork 4
Expand file tree
/
Copy pathLeetCode56.java
More file actions
99 lines (87 loc) · 3.1 KB
/
Copy pathLeetCode56.java
File metadata and controls
99 lines (87 loc) · 3.1 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
package LeetCode.array;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
public class LeetCode56 {
public List<Interval> merge(List<Interval> intervals) {
List<Interval> result = new ArrayList<>();
if(intervals == null || intervals.size() == 0) return result;
intervals.sort(new Comparator<Interval>() {
@Override
public int compare(Interval o1, Interval o2) {
if(o1.start > o2.start) return 1;
else if(o1.start < o2.start) return -1;
else return 0;
}
});
System.out.println(intervals.toString());
result.add(intervals.get(0));
System.out.println(result.toString());
for(int i = 1; i < intervals.size(); i++){
Interval current = intervals.get(i);
Interval reEnd = result.get(result.size()-1);
if(current.start <= reEnd.end){
Interval ob = new Interval(reEnd.start, current.end);
if(current.end < reEnd.end){
ob = new Interval(reEnd.start, reEnd.end);
}
result.set(result.size()-1, ob);
} else {
result.add(current);
}
System.out.println(result.toString());
}
return result;
}
class Interval{
Integer start;
Integer end;
public Interval(int start, int end) {
this.start = start;
this.end = end;
}
public Interval() {
this.start = 0;
this.end = 0;
}
@Override
public String toString() {
return "Interval{" +
"start=" + start +
", end=" + end +
'}';
}
}
//--------------------------------------------------------
public List<Interval> merge2(List<Interval> intervals) {
if(intervals.size() <= 1) return intervals;
intervals.sort((i1, i2) -> Integer.compare(i1.start, i2.start));
List<Interval> result = new ArrayList<>();
int start = intervals.get(0).start;
int end = intervals.get(0).end;
for(Interval interval : intervals){
if(end >= interval.start){
end = Math.max(end, interval.end);
}else {
result.add(new Interval(start, end));
start = interval.start;
end = interval.end;
}
}
result.add(new Interval(start, end));
return result;
}
public static void main(String[] args) {
LeetCode56 instance = new LeetCode56();
Interval o1 = instance.new Interval(1,3);
Interval o2 = instance.new Interval(2,6);
Interval o3 = instance.new Interval(8,10);
Interval o4 = instance.new Interval(15,18);
List<Interval> list = new ArrayList<>();
list.add(o1);
list.add(o2);
list.add(o3);
list.add(o4);
instance.merge(list);
}
}