C++ In Practice - Interval Problems

Interval Problems (C++11 Deep Dive)

Interval problems rely heavily on Sorting and Greedy strategies. In C++11, the efficiency of these solutions often hinges on how you manage memory layout (structures vs. vectors of vectors) and how effectively you utilize STL algorithms like std::sort with custom lambdas and std::priority_queue.

Data Representation: The Architecture Choice

In many coding challenges (e.g., LeetCode), inputs are provided as std::vector<std::vector<int>>. Under the Hood: A vector<vector<int>> is a "jagged array." It is a dynamic array of pointers, where each pointer points to another dynamic array on the heap.

• Cache Locality: Poor. Traversing this requires jumping around heap memory.
• Overhead: High. Each inner vector has its own control block (size, capacity, pointer).

Optimization (Safety Critical / High Perf): Always prefer a flat struct or std::pair stored in a single vector.

struct Interval {
    int start;
    int end;
};
// Contiguous memory block. Excellent cache locality.
std::vector<Interval> intervals; 

Note: The solutions below use vector<vector<int>> , but keep the optimization in mind.

---

1. Merge Intervals

Input: An unsorted array of intervals where intervals[i] = [start_i, end_i]. Condition: Intervals may overlap partially, completely encapsulate one another, or remain disjoint. Output: An array of strictly non-overlapping intervals that continuously cover the exact same temporal ranges as the input.

Visual Constraints:

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

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

Pattern: Sort by Start Time + Linear Scan.

Complexity: Time O(N log N) | Space O(N) (for output).

C++11 Deep Dive:

• Lambda Comparator: We pass a lambda to std::sort to avoid writing a separate functor struct.
• Reference Access: We use result.back() to access the "active" interval we are merging into, avoiding index management variables.

#include <vector>
#include <algorithm>
#include <cmath> // for std::max

std::vector<std::vector<int>> merge(std::vector<std::vector<int>>& intervals) {
    if (intervals.empty()) return {};

    // 1. Sort by start time using C++11 Lambda
    // Captures: [] (none), Params: (const reference to avoid copy)
    std::sort(intervals.begin(), intervals.end(), 
              [](const std::vector<int>& a, const std::vector<int>& b) {
                  return a[0] < b[0];
              });

    std::vector<std::vector<int>> result;
    // Push the first interval to start
    result.push_back(intervals[0]);

    for (size_t i = 1; i < intervals.size(); ++i) {
        // Reference to the last interval in result (the one we might merge into)
        // usage of & is critical to modify it in-place.
        std::vector<int>& lastMerged = result.back();
        const std::vector<int>& current = intervals[i];

        if (current[0] <= lastMerged[1]) {
            // Overlap detected: Extend the end time
            lastMerged[1] = std::max(lastMerged[1], current[1]);
        } else {
            // No overlap: Push new interval
            result.push_back(current);
        }
    }

    return result;
}

---

2. Insert Interval

Input:

1. An array of non-overlapping intervals sorted in ascending order by start_i.
2. A single newInterval = [start, end]. Condition: The insertion of newInterval may bridge, overlap, or encapsulate existing intervals, violating the non-overlapping property. Output: A new sorted array of non-overlapping intervals incorporating newInterval, with necessary merges executed to restore the non-overlapping constraint.

Visual Constraints:

Existing:
[1, 2]       :  |-|
[3, 5]       :      |---|
[6, 7]       :            |-|
[8, 10]      :                |---|
[12, 16]     :                        |-------|

Insert [4, 8]:         |-------|

Output:
[1, 2]       :  |-|
[3, 10]      :      |-------------|
[12, 16]     :                        |-------|

Pattern: Linear Scan (Parse Before, Parse Merge, Parse After).

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

Logic: Since the input is already sorted, we don't need std::sort. We simply rebuild the list in a single pass.

#include <vector>
#include <algorithm>

std::vector<std::vector<int>> insert(std::vector<std::vector<int>>& intervals, std::vector<int>& newInterval) {
    std::vector<std::vector<int>> result;
    size_t i = 0;
    size_t n = intervals.size();

    // Phase 1: Add intervals that end strictly before the new interval starts
    while (i < n && intervals[i][1] < newInterval[0]) {
        result.push_back(intervals[i]);
        i++;
    }

    // Phase 2: Merge overlapping intervals
    // Condition: Interval starts before newInterval ends
    while (i < n && intervals[i][0] <= newInterval[1]) {
        newInterval[0] = std::min(newInterval[0], intervals[i][0]);
        newInterval[1] = std::max(newInterval[1], intervals[i][1]);
        i++;
    }
    // Push the merged "super-interval"
    result.push_back(newInterval);

    // Phase 3: Add remaining intervals
    while (i < n) {
        result.push_back(intervals[i]);
        i++;
    }

    return result;
}

---

3. Non-overlapping Intervals (Erase Overlaps)

Input: An unsorted array of intervals where intervals[i] = [start_i, end_i].

Condition: Intervals overlap. A greedy choice must be made to maximize the number of retained intervals.

Output: The absolute minimum integer count of intervals that must be deleted to eliminate all overlaps.

Visual Constraints:

Input:
[1, 2]       :  |-|
[2, 3]       :    |-|
[3, 4]       :      |-|
[1, 3]       :  |---|  <- Deleting this overlapping interval saves [1,2] and [2,3].

Output: 1 (The interval [1, 3] is removed).

Pattern: Greedy Strategy (Sort by END Time).

Complexity: Time O(N log N) | Space O(1) (ignoring sort stack).

Key Insight: Why sort by end time? If we pick the interval that ends earliest, we leave the maximum amount of "free time" for subsequent intervals, thereby minimizing the number of intervals we must remove.

#include <vector>
#include <algorithm>

int eraseOverlapIntervals(std::vector<std::vector<int>>& intervals) {
    if (intervals.empty()) return 0;

    // SORT BY END TIME
    std::sort(intervals.begin(), intervals.end(), 
              [](const std::vector<int>& a, const std::vector<int>& b) {
                  return a[1] < b[1];
              });

    int removeCount = 0;
    // Track the end of the last valid interval added to our "non-overlapping set"
    int prevEnd = intervals[0][1];

    for (size_t i = 1; i < intervals.size(); ++i) {
        if (intervals[i][0] < prevEnd) {
            // Collision: Current interval starts before previous ended.
            // Greedy decision: We keep the previous one (because it ended earlier,
            // verified by sort order), and "remove" the current one.
            removeCount++;
        } else {
            // No collision: Update end time
            prevEnd = intervals[i][1];
        }
    }

    return removeCount;
}

---

4. Meeting Rooms II

Input: An unsorted array of meeting time intervals where intervals[i] = [start_i, end_i].

Condition: Overlapping intervals cannot share the same resource (room).

Output: The minimum integer count of parallel resources (rooms) required to execute all intervals simultaneously without collision.

Visual Constraints:

Input:
[0, 30]      :  |----------------------------|
[5, 10]      :       |---|
[15, 20]     :                 |---|

Execution State (Resource Allocation):
Room 1       :  |----------------------------|  <- [0, 30] occupies Room 1 continuously.
Room 2       :       |---|     |---|            <- [5, 10] and [15, 20] can share Room 2 sequentially.

Output: 2

Pattern: Min-Heap (Priority Queue) or Sweep Line.

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

Deep Dive (Min-Heap Approach): We simulate the timeline.

1. Sort meetings by Start Time.
2. Use a Min-Heap to store the End Times of active meetings.
3. The top of the heap is the meeting that ends earliest.
4. If a new meeting starts after the heap top ends, we can reuse that room (pop the heap).
5. Always push the new meeting's end time.
6. Heap size = minimum rooms needed.

C++11 Note: std::priority_queue is a Max-Heap by default. To make it a Min-Heap, we must specify the underlying container (std::vector) and the comparator (std::greater).

#include <vector>
#include <algorithm>
#include <queue> // for std::priority_queue
#include <functional> // for std::greater

int minMeetingRooms(std::vector<std::vector<int>>& intervals) {
    if (intervals.empty()) return 0;

    // 1. Sort by Start Time
    std::sort(intervals.begin(), intervals.end(), 
              [](const std::vector<int>& a, const std::vector<int>& b) {
                  return a[0] < b[0];
              });

    // 2. Min-Heap for End Times
    // Syntax: <Type, Container, Comparator>
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

    // Add first meeting's end time
    minHeap.push(intervals[0][1]);

    for (size_t i = 1; i < intervals.size(); ++i) {
        // If the earliest ending meeting finishes before the new one starts...
        if (intervals[i][0] >= minHeap.top()) {
            minHeap.pop(); // ...vacate that room (reuse it)
        }
        
        // Push the current meeting's end time (either into a new room, 
        // or the reused room - conceptually same operation)
        minHeap.push(intervals[i][1]);
    }

    // The size of the heap represents the concurrent overlap count
    return minHeap.size();
}

---

5. Advanced: The Sweep Line Algorithm

The Sweep Line is an algorithmic paradigm, not a specific problem. It calculates peak concurrent resource utilization, solving the exact mathematical requirement of the Meeting Rooms II problem without requiring a Priority Queue (Min-Heap).

Execution Mechanics

It decomposes continuous intervals into discrete, atomic point events on a chronological timeline. A theoretical vertical line "sweeps" across this timeline from left to right, sequentially updating a global state integer.

1. Decomposition: Every interval [start, end] generates two independent events:

• (start, +1) representing resource acquisition.
• (end, -1) representing resource release.

2. Chronological Sorting: All events are merged into a single array and sorted ascending by time.

• Collision Rule: If an end event and a start event share the exact same timestamp, the end event must be processed strictly before the start event. This releases the resource before the new operation claims it, preventing false positive overlaps at exact interval boundaries.

3. State Accumulation: The algorithm iterates linearly through the sorted event queue, accumulating the +1 and -1 values into a running counter. The maximum integer recorded in this counter during the entire traversal represents the absolute peak concurrency limit.

Conceptual Execution State

Input Intervals: [1, 5], [2, 6], [4, 5]

Event Generation (Unsorted): [1, +1], [5, -1], [2, +1], [6, -1], [4, +1], [5, -1]

Sorted Event Queue: [1, +1], [2, +1], [4, +1], [5, -1], [5, -1], [6, -1]

Sweep Line Iteration (Linear Scan):

Time 1:  +1 -> Current: 1 | Max: 1
Time 2:  +1 -> Current: 2 | Max: 2
Time 4:  +1 -> Current: 3 | Max: 3  <-- Peak Overlap Detected
Time 5:  -1 -> Current: 2 | Max: 3
Time 5:  -1 -> Current: 1 | Max: 3
Time 6:  -1 -> Current: 0 | Max: 3

Result: 3 parallel resources required.

Concept: Break intervals into atomic "Events": (time, +1) for start, (time, -1) for end. Sort events by time. Walk through events and track the running sum.

Visualizing the Data Structure:

Intervals: [1, 5], [2, 6], [4, 5]

Events Vector:
[ {1, +1}, {2, +1}, {4, +1}, {5, -1}, {5, -1}, {6, -1} ]
Sort Criteria: Time asc. If times equal, process END (-1) before START (+1) to avoid false overlap.

Implementation:

#include <vector>
#include <algorithm>

int minMeetingRoomsSweepLine(std::vector<std::vector<int>>& intervals) {
    std::vector<std::pair<int, int>> events;
    events.reserve(intervals.size() * 2);

    for (const auto& iv : intervals) {
        events.push_back({iv[0], 1});  // Start
        events.push_back({iv[1], -1}); // End
    }

    // Sort events
    std::sort(events.begin(), events.end(), 
              [](const std::pair<int, int>& a, const std::pair<int, int>& b) {
                  if (a.first != b.first) return a.first < b.first;
                  // If times are equal, process -1 (End) before 1 (Start)
                  return a.second < b.second; 
              });

    int maxRooms = 0;
    int currentRooms = 0;

    for (const auto& event : events) {
        currentRooms += event.second;
        if (currentRooms > maxRooms) {
            maxRooms = currentRooms;
        }
    }
    return maxRooms;
}

Summary of Interval Patterns

Problem	Sort Criteria	Key Data Structure	Logic
Merge Intervals	Start Time	vector (Stack behavior)	current.start <= last.end ? Merge : Push
Insert Interval	None (Preserved)	vector (Builder)	1. Add Pre, 2. Merge Loop, 3. Add Post
Non-Overlapping	End Time	int prevEnd	Greedy. If overlap, keep the one ending first.
Meeting Rooms II	Start Time	priority_queue (Min)	Heap stores end times. start >= heap.top ? Pop.
Meeting Rooms II	Events (Sweep)	vector<pair>	Flatten to points. Sort. Prefix Sum.