Data Structures & Algorithms in Java – Intervals – Merge Intervals

Problem:

Given an array of intervals , merge overlapping intervals and return the non overlapping array of intervals.

For example,

Given the array:

[[1,3],[2,6],[8,10]]

The output should be

[[1,6],[8,10]]

Try out the solution here:

https://leetcode.com/problems/merge-intervals/

Solution:

First sort the array , this makes it easier to merge overlapping intervals.

Once sorted , compare two successive intervals starting from the first. If they overlap merge them.

ALGORITHM:

STEP 1: Sort the array of intervals based on the start value

STEP 2: Create an output array

STEP 3: Iterate through the array and for each interval , check if the start of the interval overlaps with the end of the previous interval, if so merge the two else add the new interval to the output (to merge , take the maximum of the end values of the two intervals and use that as the end value of the merged interval , start value remains the same as that of the previous interval).

For the first interval there wont be any previous interval so add it to the output.

STEP 4: Return the output array

Code:

class Solution {
    public int[][] merge(int[][] intervals) {
        
        
        
       
        
        Arrays.sort(intervals,(first,second) -> Integer.compare(first[0],second[0]));
        
        var output = new LinkedList<int[]>();
        
      for(int[] i:intervals){
            
           if(output.isEmpty() || output.getLast()[1] < i[0]){
                
                
                output.add(i);
            }else{
                
             
                output.getLast()[1] = Math.max(output.getLast()[1],i[1]);
            }
            
            
        }
        
        return output.toArray(new int[output.size()][2]);
    }
}

Time complexity is O(nlogn) since you do sorting first it takes O(nlogn) and then again you do a pass through the input array which takes O(n). Total time complexity can be considered as O(nlogn).

Space complexity is O(n) for the output array.

That’s it!