#include <stdio.h>
#include <stdlib.h>
/* Simple struct to represent an interval [start, end] */
typedef struct {
int start;
int end;
} Interval;
/* Comparison function for qsort: sort by start time */
int cmpIntervals(const void *a, const void *b) {
Interval *x = (Interval *)a;
Interval *y = (Interval *)b;
return x->start - y->start;
}
/*
* Find common free time:
* 1. Sort intervals
* 2. Merge overlapping intervals
* 3. Gaps between merged intervals are free time
*/
int findCommonFreeTime(Interval *intervals, int n, Interval *freeTime) {
if (n == 0) return 0;
/* Step 1: Sort intervals by start time */
qsort(intervals, n, sizeof(Interval), cmpIntervals);
/* Step 2: Merge intervals into a temporary array */
Interval *merged = malloc(n * sizeof(Interval));
int m = 0; // merged count
merged[m++] = intervals[0];
for (int i = 1; i < n; i++) {
Interval *last = &merged[m - 1];
if (intervals[i].start <= last->end) {
/* Overlapping → extend the merged interval */
if (intervals[i].end > last->end)
last->end = intervals[i].end;
} else {
/* No overlap → add new merged interval */
merged[m++] = intervals[i];
}
}
/* Step 3: Find gaps between merged intervals */
int freeCount = 0;
for (int i = 1; i < m; i++) {
int start = merged[i - 1].end;
int end = merged[i].start;
if (start < end) {
freeTime[freeCount].start = start;
freeTime[freeCount].end = end;
freeCount++;
}
}
free(merged);
return freeCount;
}
int main() {
Interval intervals[] = {
{2,3}, {4,5}, {7,11}, {1,5}, {6,9}
};
int n = sizeof(intervals) / sizeof(intervals[0]);
/* Allocate space for free-time results */
Interval freeTime[10];
int freeCount = findCommonFreeTime(intervals, n, freeTime);
/* Print results */
for (int i = 0; i < freeCount; i++) {
printf("[%d,%d] ", freeTime[i].start, freeTime[i].end);
}
}
/*
run:
[5,6]
*/
