Mastering Merge Intervals: From Basics to Brilliance (with Real Problems & Open Source Impact)

🧠 What Is the Merge Intervals Algorithm?

Definition:
The Merge Intervals algorithm combines overlapping intervals in a list of ranges into a minimized set of non-overlapping intervals.

Use Cases:

• Booking systems (calendar conflicts)

• CPU/GPU scheduling

• Memory management

• Flight timings

• Video compression (frame merge)

• Event management systems

---

🧭 Mind Shortcuts to Remember Merge Intervals

• Sort First – Always sort intervals by starting point!

• Think Timeline – Like booking rooms: If one meeting ends before the next begins, no overlap.

• Compare Two at a Time – Merge overlapping intervals while moving forward.

• Store Result – Use a result array/list to build your final set.

---

🧪 Example: Merge Overlapping Meetings

Input:

cpp

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

Expected Output:

cpp

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

Why?

• [1, 3] and [2, 6] overlap ⇒ merge to [1, 6]

• [8, 10] and [15, 18] don't overlap ⇒ remain separate

---

🧱 Brute Force (Naïve/Linear) Approach

Steps:

1. Compare every pair of intervals.

2. If they overlap, merge them.

3. Continue until no more merging is possible.

Time Complexity:

• Worst Case: O(n^2)

• Space: O(n) (for merged list)

Pseudocode (C++-like):

cpp
vector<vector<int>> mergeBrute(vector<vector<int>>& intervals) {
    int n = intervals.size();
    vector<bool> merged(n, false);
    vector<vector<int>> result;

    for(int i = 0; i < n; i++) {
        if (merged[i]) continue;
        int start = intervals[i][0], end = intervals[i][1];

        for(int j = i + 1; j < n; j++) {
            if (!merged[j] && !(end < intervals[j][0] || start > intervals[j][1])) {
                start = min(start, intervals[j][0]);
                end = max(end, intervals[j][1]);
                merged[j] = true;
            }
        }
        result.push_back({start, end});
    }
    return result;
}

---

🚀 Optimized Approach (Using Sorting)

Idea:
Sort intervals by start time. Then linearly check and merge overlapping intervals.

Steps:

1. Sort intervals by their start.

2. Initialize merged list with the first interval.

3. Iterate through the rest:

   • If overlapping with last in merged → merge.

   • Else → add as new interval.

---

C++ Code (Optimized):

cpp
vector<vector<int>> merge(vector<vector<int>>& intervals) {
    if (intervals.empty()) return {};
    sort(intervals.begin(), intervals.end());

    vector<vector<int>> merged;
    merged.push_back(intervals[0]);

    for (int i = 1; i < intervals.size(); i++) {
        if (merged.back()[1] >= intervals[i][0]) {
            merged.back()[1] = max(merged.back()[1], intervals[i][1]);
        } else {
            merged.push_back(intervals[i]);
        }
    }
    return merged;
}

---

🧮 Time & Space Complexities:

---

❓ Must-Practice LeetCode/DSA Problems

---

🔗 Open Source Contribution – Be a Part of the Journey!

This blog post is part of a larger open-source DSA initiative that I’ve been building from the ground up on GitHub. The goal is simple:
📌 Create a one-stop repository for all major DSA patterns like Merge Intervals, Sliding Window, Prefix Sum, Binary Search, and more—
🔥 With clean explanations, code templates, space/time complexities, and beginner-friendly guides.

I believe learning together is growing together. Whether you're a beginner brushing up on LeetCode patterns or a developer looking to give back to the community:

➡️ Come contribute, learn, or simply ⭐️ star the repository to support the project.

---

👉 🔗 Visit My GitHub Repository
You’ll find well-documented, categorized DSA patterns and problems including this one—Merge Intervals!

💡 Want to contribute your own implementations or explanations? Just fork, make your changes, and create a pull request.
Let’s make the best free DSA resource together!

---

🎯 Final Thoughts

Merge Intervals isn’t just a DSA topic. It builds the foundation for handling real-world range-based problems. Whether you're building a calendar app, a booking platform, or a resource allocator — knowing how to merge intervals will always give you an edge!