Problem Statement :-
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..
Example 1:
Input: intervals=[[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation : Since intervals [1,3] and [2,6] are overlapping we can merge them to form [1,6]
intervals.
So, in this problem, we need to merge those intervals which are overlapping, which means intervals that start point lies between the start & endpoint of another interval.
Solution 1
step-1 first, we need to sort the intervals
on the basis of their starting point. by doing this we can easily merge overlapping adjacent intervals.
sorted intervals
step-2 take the interval and compare its end
with the next interval start
.
1 if they overlap, update the
end
of the first interval with the max end of overlapping intervals.2 if they do not overlap, move to the next interval.
See below the java version of this approach.
Java
class Solution {
public int[][] merge(int[][] intervals) {
final int start =0, end =1;
List<int[]> validIntervals = new ArrayList<>();
// sort the array by thier starting point
Arrays.sort(intervals,(a,b)-> Integer.compare(a[0],b[0]));
// store first interval as valid
validIntervals.add(intervals[start]);
for(int i=1; i<intervals.length;i++){
int[] interval = intervals[i];
int[] validInterval = validIntervals.get(validIntervals.size()-1);
// if intervals overlapping,then marge
if(validInterval[end] >= interval[start]){
validInterval[end] = Math.max(interval[end],validInterval[end]);
}else{
validIntervals.add(interval);
}
}
return validIntervals.toArray(new int[validIntervals.size()-1][]);
}
}
Time Complexity : sorting the intervals array + traversing through the array => O(nlogn) + O(n)
Space Complexity : creating a new n size of array => O(n)
Thank you for reading this blog. if you find something wrong, let me know in the comment section.
Top comments (0)