🚀 Mastering Intervals in DSA: A Complete Guide with Dry Runs, C++ Code & Templates

🚀 Mastering Intervals: A Key DSA Pattern for Interviews

Intervals are a cornerstone of Data Structures and Algorithms (DSA), appearing frequently in technical interviews due to their practical relevance. From scheduling meetings to managing resources, intervals—represented as pairs [start, end]—are everywhere. This guide will break down the Interval pattern, explore its real-world applications, dissect common overlap scenarios, and provide optimized solutions to popular LeetCode problems with C++ code and dry runs. Let’s dive in and add this powerful tool to your DSA arsenal!

---

💼 Why Intervals Matter: Real-World Applications

Interval problems are not just theoretical constructs for whiteboard challenges; they are at the heart of many real-world applications.

• Calendar and Event Management: Imagine finding an empty slot for a meeting between two busy colleagues. Their calendars are full of intervals (existing meetings). The task is to find a common, empty interval where a new meeting can be booked. This involves identifying separate or overlapping periods and then locating available windows.

• Project Scheduling: In project management, tasks often have start and end dates. Some tasks might have dependencies (one must finish before another begins), or they might overlap with shared resources. Interval logic helps in optimizing timelines, identifying bottlenecks, and ensuring sequential completion.

• Resource Allocation: Whether it's booking a room, allocating server time, or managing equipment usage, intervals help determine availability and prevent double-booking.

• Data Aggregation and Analysis: In data science, you might have data points that fall within certain ranges. Interval operations can help in merging these ranges for simpler analysis or identifying periods of activity.

These scenarios clearly illustrate why a strong grasp of interval problems is invaluable for any software engineer.

---

⚙️ Understanding Interval Overlaps

To solve interval problems, you need to understand how two intervals, A = [start_A, end_A] and B = [start_B, end_B], can interact. Here are the six possible overlap scenarios:

1. Disjoint (A before B): A ends before B starts. No overlap.
   Example: [1,3] and [5,7]
   Visualization:

    [A] [B]
   

2. Disjoint (B before A): B ends before A starts. No overlap.
   Example: [5,7] and [1,3]
   Visualization:

    [B] [A]
   

3. Partial Overlap (A overlaps B): A starts, and B begins before A ends.
   Example: [1,6] and [4,8]

   Visualization:

    [A--------]
        [B--------]
   

4. Partial Overlap (B overlaps A): B starts, and A begins before B ends.
   Example: [4,8] and [1,6]

5. A Contains B: A fully encompasses B.
   Example: [1,10] and [3,7]

   Visualization:

    [A------------]
       [B------]
   

6. B Contains A: B fully encompasses A.
   Example: [3,7] and [1,10]

   Visualization:

    [B------------]
       [A------]
   

🧠 Overlap Rule

Two intervals overlap if:

A.end >= B.start && B.end >= A.start

This rule is the foundation for detecting and handling overlaps efficiently.

---

🔧 Generic Template to Solve Interval Problems

Most interval problems can be tackled using this common pattern:

vector<vector<int>> solve(vector<vector<int>>& intervals) {
    // Step 1: Sort intervals by start time
    sort(intervals.begin(), intervals.end());

    vector<vector<int>> result;
    for (const auto& interval : intervals) {
        // Step 2: Check if current overlaps with last interval in result
        if (!result.empty() && result.back()[1] >= interval[0]) {
            // Merge by updating the end of the last interval
            result.back()[1] = max(result.back()[1], interval[1]);
        } else {
            // No overlap, add interval as-is
            result.push_back(interval);
        }
    }
    return result;
}

This template helps in problems involving merging, inserting, removing, or finding gaps in intervals.

---

🧪 Classic Interval Problems: Solutions & Code

Let’s tackle two iconic LeetCode interval problems, comparing naive and optimized approaches, with C++ code and detailed walkthroughs.

---

1️⃣ Merge Intervals (LeetCode 56)

Problem: Given an array of intervals [[start_i, end_i]], merge all overlapping intervals and return non-overlapping intervals covering all input ranges.

Example:

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

🐢 Naive Approach (Brute Force)

• Compare each interval with every other interval to detect and merge overlaps, repeating until no merges are possible.

• Time Complexity: O(N²)

• Space Complexity: O(1) or O(N)

• Not suitable for large inputs or interviews.

🐇 Optimized Approach (Sort and Iterate)

• Sort intervals by start time.

• Initialize result with the first interval.

• For each next interval:

  • If overlap → merge.

  • If not → add as a new interval.

Dry Run Example:

Input: [[0,1], [0,2], [0,3], [2,5], [10,11], [12,20], [19,20]]
Sorted: same as input

Step-by-step:
1. Start with merged = [[0,1]]
2. [0,2] overlaps with [0,1] → merge to [0,2]
3. [0,3] overlaps with [0,2] → merge to [0,3]
4. [2,5] overlaps with [0,3] → merge to [0,5]
5. [10,11] doesn't overlap → add as is
6. [12,20] doesn't overlap → add as is
7. [19,20] overlaps with [12,20] → merge to [12,20]
Final Output: [[0,5], [10,11], [12,20]]

C++ Code with Comments:

#include <vector>
#include <algorithm>

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());

        // Step 2: Initialize result with the first interval
        vector<vector<int>> merged_intervals;
        merged_intervals.push_back(intervals[0]);

        // Step 3: Iterate through remaining intervals
        for (size_t i = 1; i < intervals.size(); ++i) {
            auto& last = merged_intervals.back();

            // Check if current interval overlaps with the last one
            if (intervals[i][0] <= last[1]) {
                // Merge intervals by updating the end time
                last[1] = max(last[1], intervals[i][1]);
            } else {
                // No overlap: add as a new interval
                merged_intervals.push_back(intervals[i]);
            }
        }
        return merged_intervals;
    }
};

Time Complexity: O(N log N)
Space Complexity: O(N)

---

2️⃣ Insert Interval (LeetCode 57)

Problem: Given a sorted array of non-overlapping intervals and a new interval, insert the new interval and merge overlaps to maintain sorted, non-overlapping intervals.

Example:

Input: [[1,3], [6,9]], newInterval = [2,5]
Output: [[1,5], [6,9]]

🐇 Optimized Approach (Single Pass)

Dry Run:

Input: [[1,3], [6,9]], newInterval = [2,5]
Steps:
- [1,3] overlaps with [2,5] → merge to [1,5]
- [6,9] comes after → add both [1,5] and [6,9]
Output: [[1,5], [6,9]]

C++ Code with Comments:

#include <vector>
#include <algorithm>

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> result;
        bool added = false;

        for (const auto& interval : intervals) {
            if (interval[1] < newInterval[0]) {
                // Current interval ends before new interval starts
                result.push_back(interval);
            } else if (interval[0] > newInterval[1]) {
                // Current interval starts after new interval ends
                if (!added) {
                    result.push_back(newInterval);
                    added = true;
                }
                result.push_back(interval);
            } else {
                // Overlapping intervals, merge them
                newInterval[0] = min(newInterval[0], interval[0]);
                newInterval[1] = max(newInterval[1], interval[1]);
            }
        }

        // If newInterval wasn't added yet
        if (!added) result.push_back(newInterval);
        return result;
    }
};

Time Complexity: O(N)
Space Complexity: O(N)

---

🌟 When to Use the Interval Pattern

Use this pattern if you're:

• Working with ranges, time slots, or segments.

• Detecting overlaps or merging/inserting/removing intervals.

• Finding gaps or free slots.

• Able to sort intervals efficiently.

🏋️ Practice Problems to Master Intervals

• Merge Intervals (56)

• Insert Interval (57)

• Meeting Rooms II (253)

• Non-overlapping Intervals (435)

---

🎉 Conclusion: A Versatile DSA Tool

The Interval pattern is a powerful, elegant approach to solving scheduling, resource allocation, and range-based problems. By mastering overlap detection and the "sort and iterate" strategy, you’ll tackle interview questions with confidence and build robust applications. Practice these problems, internalize the overlap rule, and add this versatile tool to your DSA toolkit!

---

🔗 Stay Connected with AlgoAvengers

Join our community for more DSA insights, career guidance, and job updates:

• LinkedIn: AlgoAvengers

• Telegram: Free Courses & Internships

• Tutorials: AlgoAvengers on Hashnode

• Author: Amit kumar Meena

Subscribe to our newsletter for more DSA tips and career advice!

---