Merge Overlapping Intervals Editorial

Practice Problem Link: Merge Overlapping Intervals | Practice Problem

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given a list of intervals, merge them to get a list of non-overlapping intervals.

Naive Approach

A simple approach is to start from the first interval and check it with the rest of the intervals. If it overlaps with any of the intervals then take the intersection of both the intervals and remove the second interval. Repeat this process for every interval in the array.

After getting all non-overlapping intervals, arrange them in increasing order according to the start element by taking the minimum element one at a time.

Analysis

• Time Complexity: O(n²)
• Auxiliary Space Complexity: O(1)

Implementation

C++

vector<vector<int> > mergeIntervals(vector<vector<int> > &intervals) {
   int n = intervals.size();
   for (int i = 0; i < n; i++) {
       int currentStart = intervals[i][0], currentEnd = intervals[i][1];
       for (int j = 0; j< n; j++) {
           if (i == j) {
               continue;
           }
           if (currentStart <= intervals[j][1] && currentStart >= intervals[j][0]) {
               currentStart = min(currentStart, intervals[j][0]);
               currentEnd = max(currentEnd, intervals[j][1]);
               intervals[j][0] = INT_MAX;
               intervals[j][1] = INT_MAX;
           } else if(currentEnd <= intervals[j][1] && currentStart >= intervals[j][0]) {
               currentStart = min(currentStart, intervals[j][0]);
               currentEnd = max(currentEnd, intervals[j][1]);
               intervals[j][0] = INT_MAX;
               intervals[j][1] = INT_MAX;
           }
       }
       intervals[i][0] = currentStart;
       intervals[i][1] = currentEnd;
   }
   int totalIntervals = 0;
   for (int i = 0; i < n; i++) {
       if(intervals[i][0] != INT_MAX) {
           totalIntervals++;
       }
   }
   vector<vector<int>> ans;
   for (int i = 0; i < totalIntervals; i++) {
       int currentMinStart = INT_MAX, currentMinEnd, indx = -1;
       for (int j = 0; j < n ; j++) {
           if (intervals[j][0] < currentMinStart) {
               currentMinStart = intervals[j][0];
               currentMinEnd = intervals[j][1];
               indx = j;
           }
       }
       intervals[indx][0] = INT_MAX;
       intervals[indx][1] = INT_MAX;
       ans.push_back({currentMinStart, currentMinEnd});
   }
   return ans;
}

Java

class Solution {
   int[][] mergeIntervals(int[][] intervals) {
       int n = intervals.length;
       for (int i = 0; i < n; i++) {
           int currentStart = intervals[i][0], currentEnd = intervals[i][1];
           for (int j = 0; j < n; j++) {
               if (i == j) {
                   continue;
               }
               if (currentStart <= intervals[j][1] && currentStart >= intervals[j][0]) {
                   currentStart = Math.min(currentStart, intervals[j][0]);
                   currentEnd = Math.max(currentEnd, intervals[j][1]);
                   intervals[j][0] = Integer.MAX_VALUE;
                   intervals[j][1] = Integer.MAX_VALUE;
               } else if(currentEnd <= intervals[j][1] && currentStart >= intervals[j][0]) {
                   currentStart = Math.min(currentStart, intervals[j][0]);
                   currentEnd = Math.max(currentEnd, intervals[j][1]);
                   intervals[j][0] = Integer.MAX_VALUE;
                   intervals[j][1] = Integer.MAX_VALUE;
               }
           }
           intervals[i][0] = currentStart;
           intervals[i][1] = currentEnd;
       }
       int totalIntervals = 0;
       for (int i = 0; i < n; i++) {
           if(intervals[i][0] != Integer.MAX_VALUE) {
               totalIntervals++;
           }
       }
       int[][] ans = new int[totalIntervals][2];
       int currIndex = 0;
       for (int i = 0; i < totalIntervals; i++) {
           int currentMinStart = Integer.MAX_VALUE, currentMinEnd = 0, indx = -1;
           for (int j = 0; j < n ; j++) {
               if (intervals[j][0] < currentMinStart) {
                   currentMinStart = intervals[j][0];
                   currentMinEnd = intervals[j][1];
                   indx = j;
               }
           }
           intervals[indx][0] = Integer.MAX_VALUE;
           intervals[indx][1] = Integer.MAX_VALUE;
           ans[currIndex][0] = currentMinStart;
           ans[currIndex++][1] = currentMinEnd;
       }
       return ans;
   }
}

Optimal Approach

Sorting the array first according to the starting point will help in solving the problem linearly.

The basic idea is that if an interval is not overlapping with its next interval, then it won’t overlap with any of the intervals after that as the array is sorted. So merging the intervals will be possible while traversing the array.

Analysis

• Time Complexity: O(n * log(n))
• Auxiliary Space Complexity: O(1)

Implementation

C++

vector<vector<int> > mergeIntervals(vector<vector<int> > &intervals) {
   sort (intervals.begin(), intervals.end());
   int n = intervals.size();
   for (int i = 0; i < n - 1 ; i++) {
       if(intervals[i][1] >= intervals[i + 1][0]) {
           intervals[i + 1][0] = intervals[i][0];
           intervals[i + 1][1] = max (intervals[i][1], intervals[i+1][1]);
           intervals[i][0] = - 1;
       }
   }
   vector<vector<int>> ans;
   for(int i = 0; i < n ; i++) {
       if (intervals[i][0] != - 1) {
           ans.push_back ({intervals[i][0], intervals[i][1]});
       }
   }
   return ans;
}

Java

class ArrayComparator implements Comparator<int[]> {
   public int compare(int[] first, int[] second) {
       if(first[0] > second[0]) {
           return 1;
       } else {
           return - 1;
       }
   }
}
class Solution {
   int[][] mergeIntervals(int[][] intervals) {
       Arrays.sort(intervals, new ArrayComparator());
       int n = intervals.length;
       int totalIntervals = 1;
       for (int i = 0; i < n - 1 ; i++) {
           if(intervals[i][1] >= intervals[i + 1][0]) {
               intervals[i + 1][0] = intervals[i][0];
               intervals[i + 1][1] = Math.max (intervals[i][1], intervals[i+1][1]);
               intervals[i][0] = - 1;
           }
           else {
               totalIntervals++;
           }
       }
       int[][] ans = new int[totalIntervals][2];
       int indx = 0;
       for(int i = 0; i < n ; i++) {
           if (intervals[i][0] != - 1) {
               ans[indx][0] = intervals[i][0];
               ans[indx++][1] = intervals[i][1];
           }
       }
       return ans;
   }
}