LeetCode Solution 56 - Merge Intervals

 Problem Statement

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

Example 1:

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

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

Explanation: Intervals [1,3] and [2,6] overlap, so they are merged into [1,6].

Example 2:

Input: intervals = [[1,4],[4,5]]

Output: [[1,5]]

Explanation: Intervals [1,4] and [4,5] overlap, so they are merged into [1,5].

---

Optimal Approach

Sorting + Merging Intervals (Greedy Approach)

1. Sort the intervals based on the start time.
2. Iterate through the sorted list and check if the current interval overlaps with the previous one.
3. If overlapping, merge them by updating the end time.
4. If no overlap, add the merged interval to the result list.

---

C++ Code Implementation

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

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if (intervals.empty()) return {};
        
        // Step 1: Sort intervals based on start time
        sort(intervals.begin(), intervals.end());
        
        vector<vector<int>> merged;
        for (auto& interval : intervals) {
            // If merged is empty or there is no overlap, add the interval
            if (merged.empty() || merged.back()[1] < interval[0]) {
                merged.push_back(interval);
            } else {
                // Overlapping intervals, merge by updating the end time
                merged.back()[1] = max(merged.back()[1], interval[1]);
            }
        }
        return merged;
    }
};

---

Step-by-Step Explanation

1. Sorting the intervals ensures that overlapping intervals are adjacent.
2. Initialize an empty result list merged.
3. Iterate through each interval:
   • If merged is empty or the last added interval does not overlap, add the interval.
   • If overlapping, update the end time by taking the maximum of both intervals.
4. Return the merged list as the final answer.

---

Dry Run

Input: [[1,3],[2,6],[8,10],[15,18]]

Sorted Intervals: [[1,3],[2,6],[8,10],[15,18]]

Step	Current Interval	Merged List	Action
1	[1,3]	[[1,3]]	Add to merged
2	[2,6]	[[1,6]]	Merge with [1,3]
3	[8,10]	[[1,6],[8,10]]	Add to merged
4	[15,18]	[[1,6],[8,10],[15,18]]	Add to merged

Final Output: [[1,6],[8,10],[15,18]]

---

Alternative Approaches

Brute Force (Checking All Pairs) - O(N^2) Complexity

1. Iterate through all intervals and compare every pair.
2. If two intervals overlap, merge them.
3. Continue until no further merging is possible.

🔴 Why Not? - High time complexity O(N^2), inefficient for large datasets.

Using Stack - O(N log N) Complexity

1. Sort intervals.
2. Push the first interval onto a stack.
3. Compare the top of the stack with the next interval, merge if overlapping.
4. Continue until all intervals are processed.

🔵 Why Not? - Similar to the optimal approach, but uses extra space for the stack.

---

Best Solution & Why?

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(N^2)	O(1)	Too slow for large inputs
Sorting + Stack	O(N log N)	O(N)	Uses extra space
Sorting + Greedy Merge	O(N log N)	O(N)	Most efficient

✅ The sorting + greedy merge approach is best because it balances efficiency and simplicity. Sorting is O(N log N), and merging is O(N), making it optimal.

---

Complexity Analysis

• Time Complexity: O(N log N) (due to sorting, merging takes O(N)).
• Space Complexity: O(N) (for storing results, ignoring sorting overhead).

---

Conclusion

• Best Approach: Sorting + Merging (Greedy)
• Why? It optimally merges intervals in O(N log N) time.
• Practice More:
  • Insert Interval
  • Non-overlapping Intervals
  • Meeting Rooms

💡 Like this guide? Share it and practice similar problems! 🚀