Question

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

Answer 1

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct {
    int start;
    int end;
} Interval;

// Comparison function for qsort (sort by start time)
int compareIntervals(const void *a, const void *b) {
    const Interval *ia = (const Interval *)a;
    const Interval *ib = (const Interval *)b;
    return ia->start - ib->start;
}

bool hasOverlap(Interval intervals[], int size) {
    if (size == 0) {
        return true;
    }

    // Sorting is essential because once intervals are ordered by 
    // start time, any overlap can only occur between adjacent intervals.
    qsort(intervals, size, sizeof(Interval), compareIntervals);
    // (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 < size; i++) {
        if (intervals[i].start < intervals[i-1].end) {
            return false; // Overlap found
        }
    }

    return true; // No overlap
}

int main() {
    Interval intervals[] = {
        {11,12}, {5,9}, {15,17}
    };
    int size = sizeof(intervals) / sizeof(intervals[0]);

    if (hasOverlap(intervals, size))
        printf("There are NO overlapping intervals\n");
    else
        printf("There ARE overlapping intervals\n");

    return 0;
}


/*
run:

There are NO overlapping intervals

*/

 

70+ SQL courses for beginners and professionals