Question

How to detect whether any intervals overlap in a vector of start and end times with C++

Answer 1

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

bool hasOverlap(std::vector<std::pair<int,int>> intervals) {
    if (intervals.size() < 2)
        return false;

    // Sort by start time
    sort(intervals.begin(), intervals.end());

    // Compare each interval with the previous one
    for (size_t i = 1; i < intervals.size(); i++) {
        int prevEnd = intervals[i-1].second;
        int currStart = intervals[i].first;

        if (currStart < prevEnd) {
            return true; // Overlap found
        }
    }

    return false; // No overlaps
}

int main() {
    std::vector<std::pair<int,int>> intervals = {{11,12}, {5,9}, {15,17}};

    if (hasOverlap(intervals))
        std::cout << "There ARE overlapping intervals\n";
    else
        std::cout << "There are NO overlapping intervals\n";
}



/* 
run:

There are NO overlapping intervals

*/

 

70+ SQL courses for beginners and professionals

Answer 2

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

bool hasOverlap(std::vector<std::vector<int>>& intervals) {
    if (intervals.empty()) {
        return true;
    }
    
    // Sorting is essential because once intervals are ordered by 
    // start time, any overlap can only occur between adjacent intervals.
    std::sort(intervals.begin(), intervals.end());
    // (5,9), (11,12), (15,17) 
    
    // (5,9) and (11,12) → 11 < 9? No
    // (11,12) and (15,17) → 15 < 12? No

    // The loop compares each interval with the one before it.
    for (int i = 1; i < intervals.size(); i++) {
        if (intervals[i][0] < intervals[i-1][1]) {
           
            return false; // Overlap found
        }
    }
    
    return true; // No overlap
}

int main() {
    std::vector<std::vector<int>> intervals = {{11,12}, {5,9}, {15,17}};

    if (hasOverlap(intervals))
        std::cout << "There are NO overlapping intervals\n";
    else
        std::cout << "There ARE overlapping intervals\n";
}



/*
run:
 
There are NO overlapping intervals
 
*/

 

70+ SQL courses for beginners and professionals