PROBLEM DESCRIPTION
Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.
SOLUTION
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
class Solution {
public int[][] merge(int[][] intervals) {
//sort based on start of the intervals
Arrays.sort(intervals, (o1, o2) -> o1[0] > o2[0]?1: (o1[0] < o2[0]?-1:0) );
List<int[]> list = new ArrayList<>();
//init
list.add(intervals[0]);
//start merging from index 1
for(int i=1; i<intervals.length; i++){
//Get the end of last added interval
int previousEnd = list.get(list.size()-1)[1];
//If the previously added interval's end is more than or equal to the current interval's start, then we should merge them
if(previousEnd >= intervals[i][0]){
//to merge them, we can just update the end of previous interval which was added by max(previousEnd, currentEnd)
list.get(list.size()-1)[1] = Math.max(previousEnd, intervals[i][1]);
}else{
//if they don't merge, add this new interval
list.add(intervals[i]);
}
}
//convert to int[][]
int[][] ans = new int[list.size()][2];
for(int i=0; i<list.size(); i++){
ans[i] = list.get(i);
}
// we can also do:
// return list.toArray(new int[list.size()][]);
return ans;
}
}