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