An Interest In:
Web News this Week
- April 18, 2024
- April 17, 2024
- April 16, 2024
- April 15, 2024
- April 14, 2024
- April 13, 2024
- April 12, 2024
Striver's SDE Sheet Journey - 8 Merge Overlapping Subintervals
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 first interval and compare its end
with the next interval start
.
if they overlap, update the
end
of the first interval with the max end of overlapping intervals.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][]); }}
Thank you for reading this blog. if you find something wrongs, let me know in the comment section.
Original Link: https://dev.to/sachin26/strivers-sde-sheet-journey-8-merge-overlapping-subintervals-4jff
Dev To
An online community for sharing and discovering great ideas, having debates, and making friendsMore About this Source Visit Dev To