merge/insert interval


Merge Intervals

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public List<Interval> (List<Interval> intervals) {
if (intervals == null || intervals.size() <= 1)
return intervals;
List<Interval> ans = new ArrayList<Interval>();
Collections.sort(intervals, new Comparator<Interval>(){
public int compare(Interval i1, Interval i2) {
return i1.start - i2.start;
}
});
int start = intervals.get(0).start;
int end = intervals.get(0).end;
for (Interval it : intervals) {
if (it.start <= end) {

end = Math.max(end, it.end);
} else {
ans.add(new Interval(start, end));
start = it.start;
end = it.end;
}
}
ans.add(new Interval(start, end));
return ans;
}

Insert Interval

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
public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
intervals.add(newInterval);
if (intervals.size() == 1)
return intervals;
List<Interval> ans = new ArrayList<Interval>();
Collections.sort(intervals, new Comparator<Interval>(){
public int compare(Interval i1, Interval i2) {
return i1.start - i2.start;
}
});
int start = intervals.get(0).start;
int end = intervals.get(0).end;
for (Interval it : intervals) {
if (it.start <= end) {

end = Math.max(end, it.end);
} else {
ans.add(new Interval(start, end));
start = it.start;
end = it.end;
}
}
ans.add(new Interval(start, end));
return ans;
}