Question

How to add a new interval into a sorted vector of non‑overlapping intervals in C++

Answer 1

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

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

    // 1. Add all intervals that end BEFORE the new interval starts.
    // These cannot overlap.
    while (i < n && intervals[i][1] < newInterval[0]) {
        result.push_back(intervals[i]);
        i++;
    }

    // 2. Merge all intervals that DO overlap with the new interval.
    // Overlap condition: intervals[i].start <= newInterval.end
    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++;
    }

    // Add the merged interval
    result.push_back(newInterval);

    // 3. Add all remaining intervals (those starting AFTER new interval ends)
    while (i < n) {
        result.push_back(intervals[i]);
        i++;
    }

    return result;
}

int main() {
    std::vector<std::vector<int>> intervals = {{1,3}, {6,8}, {13,18}};
    std::vector<int> newInterval1 = {9,11};

    auto updated = insertInterval(intervals, newInterval1);
    
    std::vector<int> newInterval2 = {2,5};

    updated = insertInterval(updated, newInterval2);

    std::cout << "Updated intervals:\n";
    for (auto& iv : updated) {
        std::cout << "[" << iv[0] << "," << iv[1] << "] ";
    }
}


/*
run:

Updated intervals:
[1,5] [6,8] [9,11] [13,18] 

*/

 

70+ SQL courses for beginners and professionals