</>EmbeddedInterview

Merge overlapping intervals.

Medium"Coding: Sorting & Array Problems"
#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.