Merge Intervals

Sep 24, 2023#leetcode#dsa

The Merge Intervals problem on LeetCode is a classic algorithmic problem that involves merging overlapping intervals. It’s a commonly used problem in job interviews and is a good exercise for practicing algorithmic thinking and array manipulation.

Given an array of intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

For example:

  • Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
  • Output: [[1,6],[8,10],[15,18]]
  • Explanation: In the input, the intervals [1,3] and [2,6] overlap, so they are merged into [1,6]. The other two intervals [8,10] and [15,18] do not overlap with any other intervals, so they remain unchanged in the output.

The goal is to take a list of intervals and combine any overlapping intervals into a single interval. This problem is often solved by first sorting the intervals based on their start times and then iterating through the sorted list to merge overlapping intervals.

Here’s solution in C++:

#include <iostream>
#include <algorithm>
#include <vector>
#include <cassert>
using namespace std;

vector<vector<int>> merge(vector<vector<int>> &intervals) {
  // sort the intervals by their start time
  sort(intervals.begin(), intervals.end());

  // initialize the output array
  vector<vector<int>> ans;

  // initialize the current merged interval
  vector<int> curr = intervals[0];

  // iterate over the intervals
  for (int i = 1; i < intervals.size(); i++) {
    // if the current interval overlaps with the next one
    if (curr[1] >= intervals[i][0]) {
      // update the end time of the current merged interval
      curr[1] = max(curr[1], intervals[i][1]);
    } else {
      // add the current merged interval to the output array
      // start a new merged interval with the next one
      curr = intervals[i];

  // add the last merged interval to the output array

  // return the output array
  return ans;

int main() {
  // Test cases with assertions
  vector<vector<int>> intervals1 = {{1,3},{2,6},{8,10},{15,18}};
  vector<vector<int>> result1 = merge(intervals1);
  vector<vector<int>> expected1 = {{1,6},{8,10},{15,18}};
  assert(result1 == expected1);

  vector<vector<int>> intervals2 = {{1,4},{4,5}};
  vector<vector<int>> result2 = merge(intervals2);
  vector<vector<int>> expected2 = {{1,5}};
  assert(result2 == expected2);

  vector<vector<int>> intervals3 = {{1,2},{3,4},{5,6}};
  vector<vector<int>> result3 = merge(intervals3);
  vector<vector<int>> expected3 = {{1,2},{3,4},{5,6}};
  assert(result3 == expected3);

  vector<vector<int>> intervals4 = {{1,4},{0,4},{5,9}};
  vector<vector<int>> result4 = merge(intervals4);
  vector<vector<int>> expected4 = {{0,4},{5,9}};
  assert(result4 == expected4);

  cout << "All test cases passed!" << endl;

  return 0;

Time Complexity: Sorting the intervals based on their start times takes O(nlogn) time, where n is the number of intervals. Iterating through the sorted intervals once takes O(n) time since we process each interval exactly once. The dominant factor is the sorting step, so the overall time complexity is O(nlogn) due to the sorting operation.

The space complexity of the solution is O(n), where n is the number of intervals, as we use a new array mergedIntervals to store the merged intervals.