criskgl
10/16/2019 - 9:54 AM
merge intervals
Given a collection of intervals, merge all overlapping intervals.
Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
class Solution {
public int[][] merge(int[][] intervals) {
while(true){
boolean changes = false;
loopie:
for(int i = 0; i < intervals.length; i++){
int[] interval1 = intervals[i];
int beg1 = interval1[0];
int end1 = interval1[1];
for(int j = i+1; j < intervals.length; j++){
int[] interval2 = intervals[j];
int beg2 = interval2[0];
int end2 = interval2[1];
int beg3 = 0;
int end3 = 0;
if(beg1 == beg2 && end1 == end2) continue;
if(beg1 >= beg2 && beg1 <= end2 || end1 <= end2 && end1 >=beg2){
changes = true;
beg3 = Math.min(beg1,beg2);
end3 = Math.max(end1,end2);
}
else if(beg2 >= beg1 && beg2 <= end1 || end2 <= end1 && end2 >=beg1){
changes = true;
beg3 = Math.min(beg1,beg2);
end3 = Math.max(end1,end2);
}
if(changes){
intervals[i][0] = beg3;
intervals[i][1] = end3;
intervals[j][0] = beg3;
intervals[j][1] = end3;
i = 0;
j = 0;
break loopie;
}
}
}
if(!changes) break;
}
HashSet<String> unique = new HashSet<>();
for(int[] i : intervals){
unique.add(i[0]+","+i[1]);
}
int[][] result = new int[unique.size()][2];
int counter = 0;
for(String interval : unique){
String[] values = interval.split(",");
result[counter][0] = Integer.parseInt(values[0]);
result[counter][1] = Integer.parseInt(values[1]);
counter++;
}
return result;
}
}