56: Merge Intervals

[ajithh404]

Problem Number

56

Problem Title

Merge Intervals

LeetCode Link

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

Contribution Checklist

• I have written the Approach section.
• I have written the Intuition section.
• I have included a working C++ solution.
• I will raise a PR and ensure the filename follows the convention [Number]. [Problem Title].cpp.

Approach

We are given a list of intervals, and the task is to merge all overlapping intervals and return a list of non-overlapping intervals that cover all the input ranges.

1. Sort the intervals by their start times.
   This ensures that any overlapping intervals will appear consecutively.

2. Iterate through the sorted intervals:

• If the current interval does not overlap with the last merged one (i.e., its start is greater than the end of the previous interval), add it to the result list.

• Otherwise, merge the two intervals by updating the end time to be the maximum of both.

3. Return the merged list after processing all intervals.

Data structures used:

• vector<vector<int>> to store the intervals and results.

• Time Complexity: O(n log n) — due to sorting the intervals.

• Space Complexity: O(n) — for storing the merged intervals (output list).

Intuition

The key insight is that merging is only meaningful for overlapping intervals.
By sorting the intervals by their start time, we ensure that once we begin processing, any future interval that overlaps will immediately follow the current one.
Thus, a single linear pass after sorting is enough to merge all overlaps.

This approach works efficiently because sorting groups potential overlaps together and allows a single scan to resolve them all.

Solution in C++

// 56. Merge Intervals

class Solution {
 public:
  vector<vector<int>> merge(vector<vector<int>>& intervals) {
    vector<vector<int>> ans;

    // Sort intervals by starting time
    ranges::sort(intervals);

    for (const vector<int>& interval : intervals) {
      // If no overlap, add interval to result
      if (ans.empty() || ans.back()[1] < interval[0]) {
        ans.push_back(interval);
      } else {
        // Overlap detected — merge by extending the end time
        ans.back()[1] = max(ans.back()[1], interval[1]);
      }
    }

    return ans;
  }
};

[github-actions]

Hope so You have raised a valid issue, wait untill the owner will review the issue