-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathmergeIntervals.java
More file actions
75 lines (67 loc) · 1.86 KB
/
mergeIntervals.java
File metadata and controls
75 lines (67 loc) · 1.86 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
package CodingPatterns.MergeIntervals;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
/**
* Given a list of meeting intervals represented by start and end times,
* merge overlapping intervals into a minimum set of non-overlapping intervals.
*/
public class mergeIntervals {
/**
* The type Interval.
*/
static class Interval {
/**
* The Start.
*/
int start;
/**
* The End.
*/
int end;
Interval(int start,int end){
this.start=start;
this.end=end;
}
}
/**
* Merge interval list.
*
* @param intervals the intervals
* @return the list
*/
public static List<Interval> mergeInterval(List<Interval> intervals){
Collections.sort(intervals, (a,b)-> Integer.compare(a.start,b.start));
List<Interval> merged = new ArrayList<>();
Interval current = intervals.get(0);
for(int i=1;i<intervals.size();i++){
Interval next = intervals.get(i);
if(current.end>=next.start){
current.end = Math.max(current.end,next.end);
}else{
merged.add(current);
current=next;
}
}
merged.add(current);
return merged;
}
/**
* Main.
*
* @param args the args
*/
public static void main(String args[]){
List<Interval> list = new ArrayList<>();
list.add(new Interval(1,2));
list.add(new Interval(12,20));
list.add(new Interval(4,9));
list.add(new Interval(9,27));
list.add(new Interval(29,35));
list.add(new Interval(3,4));
list = mergeInterval(list);
for(int i=0;i<list.size();i++){
System.out.println(list.get(i).start+" - "+list.get(i).end);
}
}
}