Imagine you're organizing a chaotic calendar for a busy executive. You've got a list of appointments, but they're all over the place. One meeting runs from 1:00 PM to 3:00 PM, and another runs from 2:00 PM to 4:00 PM. In your head, you don't see two separate events; you just see one giant block of "busy time" from 1:00 PM to 4:00 PM. If there's a third meeting from 5:00 PM to 6:00 PM, that's a separate block because there's a gap in between. Your goal is to clean up the calendar so you only have the absolute minimum number of time blocks.

In a coding interview, this is exactly what happens when you're asked to "Merge Overlapping Intervals." We map the "appointments" to pairs of integers (start and end times), the "cleaning up" to a loop that compares adjacent intervals, and the "giant block" to a new interval that spans from the earliest start to the latest end of all overlapping segments.

The Art of the Clarification

If I were sitting next to you in an interview, the first thing I'd tell you is: do not start coding immediately. Most candidates rush into the logic and realize halfway through that they assumed the input was sorted when it wasn't. I always start by asking, "Are the intervals guaranteed to be sorted by their start time?"

If the answer is no, our first move has to be a sort. In C++, std::sort is our best friend here. Sorting the intervals allows us to process them linearly; we only ever need to compare the current interval with the last one we merged. It turns a potentially quadratic problem into an $O(N \log N)$ one.

Walking Through the Merge Logic

Let's look at how we actually implement this. I prefer using a std::vector<std::vector<int>> or a custom struct for clarity. Here is how I would write this out during a live session:

#include <vector>
#include <algorithm>
#include <iostream>

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

    // 1. Sort by the start time
    std::sort(intervals.begin(), intervals.end());

    std::vector<std::vector<int>> merged;
    
    // Start by pushing the first interval into our result set
    merged.push_back(intervals[0]);

    for (size_t i = 1; i < intervals.size(); ++i) {
        // Look at the last interval we added to the merged list
        auto& lastMerged = merged.back();
        const auto& current = intervals[i];

        // If the current interval starts before or exactly when the last one ends, they overlap
        if (current[0] <= lastMerged[1]) {
            // Merge them by extending the end time to the maximum of both
            lastMerged[1] = std::max(lastMerged[1], current[1]);
        } else {
            // No overlap, just add the current interval as a new block
            merged.push_back(current);
        }
    }

    return merged;
}

Where Most Candidates Trip Up

I've seen plenty of engineers forget the std::max call. They assume that because the intervals are sorted by start time, the second interval must also end later. That's a dangerous assumption. Consider the intervals [1, 10] and [2, 5]. The second one is completely contained within the first. If you just blindly set the end time to current[1], you'd actually shrink your merged interval from 10 down to 5, which is a bug.

Another detail: notice I used auto& lastMerged = merged.back();. Using a reference here is key. It allows us to modify the interval already inside the vector without having to pop it out, change it, and push it back in. It's cleaner and slightly more efficient.

Talking Through Complexity

At this point in an interview, the interviewer will ask about Big O. Be ready to break it down exactly like this:

• Time Complexity: $O(N \log N)$. The sorting takes the bulk of the time. The subsequent linear scan through the intervals only takes $O(N)$, but in asymptotic analysis, the $N \log N$ dominates.
• Space Complexity: $O(N)$ in the worst case (where no intervals overlap and we store every single one in the result vector), or $O(\log N)$ if you only count the auxiliary space used by the sorting algorithm.

📋 Practical Task

Implementing a Range-Based Conflict Checker

In this exercise, you will apply the interval merging logic to a different problem. Instead of merging the intervals, you need to write a function called hasConflict that determines if any two time slots in a given list overlap. This is the "detection" phase that happens before a merge.

Requirements:

• Write a function bool hasConflict(std::vector<std::pair<int, int>>& slots).
• The function should return true if any two slots overlap (even by a single unit of time, e.g., [10, 20] and [20, 30] is considered a conflict).
• You must sort the slots first to ensure efficiency.
• The time complexity should be $O(N \log N)$ and space complexity $O(1)$ beyond the sorting requirements.

// Starter code
#include <vector>
#include <algorithm>
#include <iostream>

bool hasConflict(std::vector<std::pair<int, int>>& slots) {
    // Your implementation here
}

int main() {
    std::vector<std::pair<int, int>> schedule1 = {{10, 15}, {20, 25}, {14, 18}}; // Should be true
    std::vector<std::pair<int, int>> schedule2 = {{10, 15}, {20, 25}, {30, 35}}; // Should be false
    
    std::cout << "Schedule 1 Conflict: " << (hasConflict(schedule1) ? "Yes" : "No") << std::endl;
    std::cout << "Schedule 2 Conflict: " << (hasConflict(schedule2) ? "Yes" : "No") << std::endl;
    return 0;
}