algoadvance

Leetcode 56. Merge Intervals

Problem Statement

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.

Example

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] overlap, merge them into [1,6].

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

Clarifying Questions

  1. Input Constraints:
    • Can the intervals be out of order?
    • Are the intervals always valid (i.e., does start_i always ≤ end_i)?
  2. Edge Cases:
    • What should we return if the input is an empty list?
    • What should we return if there’s only one interval in the list?

For the purposes of our solution, we will assume intervals can be out of order, intervals are always valid, and we will address edge cases in our implementation.

Strategy

  1. Sort the Intervals:
    • Sort the intervals based on the starting value. This helps us easily identify overlapping intervals.
  2. Merge Intervals:
    • Initialize a result vector to store the merged intervals.
    • Iterate over each interval and compare it with the last interval in the result vector to check for overlap:
      • If it overlaps, merge the intervals.
      • If it does not overlap, simply add the interval to the result vector.

Time Complexity

Overall time complexity: O(n log n).

Code

#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> merge(vector<vector<int>>& intervals) {
    // Edge case: if there are no intervals, return an empty vector
    if (intervals.empty()) {
        return {};
    }

    // Sort intervals by their starting point
    sort(intervals.begin(), intervals.end());

    // Vector to hold the merged intervals
    vector<vector<int>> merged;

    // Start with the first interval as the initial interval to merge
    merged.push_back(intervals[0]);

    // Iterate through the rest of the intervals
    for (auto i = 1; i < intervals.size(); ++i) {
        // Get the last merged interval
        auto& lastMerged = merged.back();

        // Compare current interval with the last merged interval
        if (intervals[i][0] <= lastMerged[1]) {
            // There is an overlap, so we merge the intervals
            lastMerged[1] = max(lastMerged[1], intervals[i][1]);
        } else {
            // No overlap, so we add the current interval to the result
            merged.push_back(intervals[i]);
        }
    }

    return merged;
}

Explanation

  1. Sorting: We sort the intervals array based on the starting value of each interval. This is achieved using the built-in sort function.
  2. Merging:
    • We initialize a merged vector and add the first interval to it.
    • For each subsequent interval, we compare it with the last interval in the merged vector.
      • If the current interval overlaps with the last merged interval (intervals[i][0] <= lastMerged[1]), we merge them by updating the end of the last merged interval (lastMerged[1] = max(lastMerged[1], intervals[i][1])).
      • If there is no overlap, we simply add the current interval to the merged vector.

Time Complexity Analysis

Thus, our total time complexity is O(n log n).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI