Merge overlapping intervals.
#include <stdlib.h>
typedef struct { int start, end; } interval_t;
static int by_start(const void *a, const void *b)
{
const interval_t *x = a, *y = b;
return (x->start > y->start) - (x->start < y->start);
}
/* merges in place; returns the new count */
size_t merge_intervals(interval_t *v, size_t n)
{
if (n == 0) return 0;
qsort(v, n, sizeof *v, by_start);
size_t w = 0;
for (size_t i = 1; i < n; i++) {
if (v[i].start <= v[w].end) { /* overlaps the current one */
if (v[i].end > v[w].end) v[w].end = v[i].end;
} else {
v[++w] = v[i];
}
}
return w + 1;
}
/* [1,3] [2,6] [8,10] [15,18] -> [1,6] [8,10] [15,18] */
Points: sort by start (O(n log n)), then one pass extending the last merged interval. Decide whether touching intervals ([1,2] and [2,3]) merge (<=) or not (<). Embedded uses: merging free regions in an allocator, combining flash erase ranges, coalescing time windows in a scheduler.