Merge Intervals (With Solution)

Given N intervals, where each interval denotes startTime and endTime. The task is to merge all overlapping intervals possible and return a list of overlapping intervals in sorted order of their startTime.

Examples:Input: 

merge overlapping intervals

Explanation: Provided in the image

Confused about your next job?

In 3 simple steps you can find your personalised career roadmap in Software development for FREE



Expand in New Tab 

 

Input:  intervals[] = {[1, 3],[2, 6],[8, 10],[15, 18]}

Output: {[1,6],[8,10],[15,18]}

Approach 1: Brute Force

First of all, let us try to understand the different types of intervals possible.

different types of intervals

The idea is to try to mark each interval as non-visited and for each intervals which is marked as non-visited, find if another interval exists, which overlaps in any form with the current interval.
If such an interval exists, merge both the intervals and mark them visited

Implementation of the Approach:

C++ Code

bool isOverlap(int minS, int maxE, vector<int> interval)
{
    if (minS > interval[1] || maxE < interval[0])
    {
        return false;
    }
 
    return true;
}
 
vector<vector<int>> mergeIntervals(vector<vector<int>> &intervals)
{
    int n = intervals.size();
    vector<vector<int>> res;
 
    vector<bool> vis(n, false);
 
    for (int i = 0; i < n; i++)
    {
        if (vis[i])
        {
            continue;
        }
 
        vis[i] = true;
        int minS = intervals[i][0];
        int maxE = intervals[i][1];
 
        while (true)
        {
            int cnt = 0;
 
            for (int j = 0; j < n; j++)
            {
                if (!vis[j] && isOverlap(minS, maxE, intervals[j]))
                {
                    vis[j] = true;
                    minS = min(minS, intervals[j][0]);
                    maxE = max(maxE, intervals[j][1]);
                    cnt++;
                }
            }
 
            if (cnt == 0)
            {
                break;
            }
        }
 
        vector<int> interval = {minS, maxE};
        res.push_back(interval);
    }
 
    sort(res.begin(), res.end());
    return res;
}

Java Code

public static List < Interval > mergeIntervals(Interval[] intervals) {
  int n = intervals.length;
  List < Interval > res = new ArrayList();
 
  boolean vis[] = new boolean[n];
 
  for (int i = 0; i < n; i++) {
    if (vis[i]) {
      continue;
    }
 
    vis[i] = true;
    int minS = intervals[i].start;
    int maxE = intervals[i].finish;
 
    while (true) {
      int c = 0;
 
      for (int j = 0; j < n; j++) {
        if (!vis[j] && isOverlap(minS, maxE, intervals[j])) {
          vis[j] = true;
          minS = Math.min(minS, intervals[j].start);
          maxE = Math.max(maxE, intervals[j].finish);
          c++;
        }
      }
 
      if (c == 0) {
        break;
      }
    }
res.add(new Interval(minS, maxE));
  }
 
  Collections.sort(res, new Comparator < Interval > () {
 
    public int compare(Interval a, Interval b) {
      if (a.start == b.start) {
        return a.finish - b.finish;
      }
 
      return a.start - b.start;
    }
 
  });
 
  return res;
}
 
public static boolean isOverlap(int minS, int maxE, Interval i) {
  if (minS > i.finish || maxE < i.start) {
    return false;
  }
 
  return true;
}

Python Code

def isOverlap(minS, maxE, i):
 
    if minS > i.end or maxE < i.start:
        return False
 
    return True
 
 
def mergeIntervals(intervals):
    n = len(intervals)
 
    res = []
 
    vis = [False for i in range(n)]
 
    for i in range(n):
        if vis[i] is True:
            continue
 
        vis[i] = True
        minS = intervals[i].start
        maxE = intervals[i].end
 
        while 1:
            cnt = 0
 
            for j in range(n):
 
                if vis[j] is False and isOverlap(minS, maxE, intervals[j]):
 
                    vis[j] = True
                    minS = min(minS, intervals[j].start)
                    maxE = max(maxE, intervals[j].end)
                    cnt += 1
            if cnt == 0:
                break
 
        a = Solution(minS, maxE)
        res.append(a)
 
    return res

Time Complexity: O(N^2), where N is total size of the interval array

Space Complexity: O(N), as visiting array is used.

Approach 2: Sorting

Since we need to merge all the possible intervals, instead of finding if an unvisited interval exists which overlaps the current interval, the intervals can be simply sorted according to their starting time.
This ensures that all the intervals are arranged in a contagious fashion.

Let us understand this with an example :

contagious fashion

Algorithm:

  • Sort the intervals array according to startTime.
  • Create an array to store the merged intervals.
  • If the current and previous intervals does not overlap each other, append the current interval to the merged array.
  • Else, merge both previous and current intervals and insert it into the merged array.

Implementation of the Approach:

C++ Code

vector < vector < int >> merge(vector < vector < int >> & intervals) {
  sort(intervals.begin(), intervals.end());
 
  vector < vector < int >> merged;
  for (auto interval: intervals) {
    if (merged.empty() || merged.back()[1] < interval[0]) {
      merged.push_back(interval);
    } else {
      merged.back()[1] = max(merged.back()[1], interval[1]);
    }
  }
  return merged;
}

Java Code

 public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        LinkedList<int[]> merged = new LinkedList<>();
        for (int[] interval : intervals) {
            if (merged.isEmpty() || merged.getLast()[1] < interval[0]) {
                merged.add(interval);
            }
            else {
                merged.getLast()[1] = Math.max(merged.getLast()[1], interval[1]);
            }
        }
        return merged.toArray(new int[merged.size()][]);
    }

Python Code

def merge(self, intervals: List[List[int]]) -> List[List[int]]:
 
    intervals.sort(key=lambda x: x[0])
 
    merged = []
    for interval in intervals:
        if not merged or merged[-1][1] < interval[0]:
            merged.append(interval)
        else:
            merged[-1][1] = max(merged[-1][1], interval[1])
 
    return merged

Time Complexity: O(NlogN), where N is total size of the array

Space Complexity: O(N), where N is total size of the merged array

Practice Questions:

Merge Overlapping Intervals

FAQ

  • What is the advantage of sorting the input array according to start time?
    Sorting the input array according to start time ensures that all the intervals are in a contagious manner, and helps in merging without having to search for the whole array again.
  • How are the intervals merged?
    The intervals are merged based on their start time and end time.
    Let us consider two intervals [a, b] and [x, y]
    Both the intervals overlap, if and only if:  b >= x
Previous Post
Egg Dropping Puzzle

Egg Dropping Puzzle

Next Post
Next Permutation

Next Permutation Problem

Total
0
Share