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.

unsorted 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.