#include <stdio.h>
#include <stdlib.h> // qsort
typedef struct {
int start;
int end;
} Interval;
/* Comparison function for qsort: sort by end time ascending */
int compareByEnd(const void *a, const void *b) {
const Interval *ia = (const Interval *)a;
const Interval *ib = (const Interval *)b;
return ia->end - ib->end;
}
/*
* Removes the minimum number of intervals so that the remaining ones do not overlap.
* Returns how many intervals must be removed.
*/
int eraseMinimumOverlaps(Interval *arr, int n) {
if (n == 0)
return 0;
/* Sort intervals by end time */
qsort(arr, n, sizeof(Interval), compareByEnd);
int removed = 0;
int lastEnd = arr[0].end;
/* Greedily keep intervals that do not overlap */
for (int i = 1; i < n; i++) {
if (arr[i].start < lastEnd) {
/* Overlap → remove this interval */
removed++;
} else {
/* No overlap → keep it and update the end marker */
lastEnd = arr[i].end;
}
}
return removed;
}
/*
* Builds a new array containing only the non-overlapping intervals.
* Returns the number of intervals kept.
*/
int keepNonOverlapping(Interval *arr, int n, Interval *out) {
if (n == 0)
return 0;
qsort(arr, n, sizeof(Interval), compareByEnd);
int count = 0;
out[count++] = arr[0];
int lastEnd = arr[0].end;
for (int i = 1; i < n; i++) {
if (arr[i].start >= lastEnd) {
out[count++] = arr[i];
lastEnd = arr[i].end;
}
}
return count;
}
int main(void) {
// The only overlap is between [5,7] and [4,10]
// To keep the most intervals, we keep the one that ends earlier → [5,7]
Interval arr[] = {{1,3}, {5,7}, {4,10}, {11,14}};
int n = sizeof(arr) / sizeof(arr[0]);
int removed = eraseMinimumOverlaps(arr, n);
Interval kept[10];
int keptCount = keepNonOverlapping(arr, n, kept);
printf("Removed: %d\nKept: ", removed);
for (int i = 0; i < keptCount; i++) {
printf("[%d,%d] ", kept[i].start, kept[i].end);
}
return 0;
}
/*
run:
Removed: 1
Kept: [1,3] [5,7] [11,14]
*//
