Merge overlapping intervals

Challenge

Merge a set of intervals so that overlapping ones become a single interval.

Task

Given an array of intervals, implement int merge_intervals(interval_t *intervals, int n) that merges all overlapping intervals in place and returns the new count. The merged intervals are written into the front of the array, sorted by start. Two intervals overlap (or touch) when a.start <= b.end and b.start <= a.end — inclusive, so [1,4] and [4,5] merge into [1,5]. The struct type is given:

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

Input

• intervals: a writable array of n interval_t values, each with start <= end. The function may reorder and overwrite it.
• n: the number of intervals (up to 1000).

Output

int: the number of merged intervals. After the call, intervals[0 .. ret-1] holds the merged set, sorted by start.

Example

{[1,3],[2,6],[8,10],[15,18]}   ->   3: {[1,6],[8,10],[15,18]}
{[1,4],[4,5]}                  ->   1: {[1,5]}    (touching merges)
{[1,5]}                        ->   1
{}                             ->   0

Edge cases

• Empty input returns 0.
• A single interval is returned unchanged.
• Touching endpoints (inclusive overlap) merge.

Rules

• O(n log n): sort by start (e.g. with qsort), then sweep once. Work in place.

Why this matters

Interval merging shows up in calendar conflicts, network bandwidth scheduling, and database query optimization (predicate pushdown). The sort-then-sweep technique is reusable across many problems.

Input format

intervals: writable array of n interval_t (given: int start, end; with start <= end); n up to 1000.

Output format

int: number of merged intervals; intervals[0..ret-1] holds them sorted by start.

Constraints

In place; use qsort. Inclusive overlap (touching intervals merge).

Starter code

typedef struct { int start; int end; } interval_t;
int merge_intervals(interval_t *intervals, int n);

Common mistakes

Using strict inequality for overlap (a.end < b.start instead of a.end >= b.start); not sorting first; merging only adjacent in the original order.

Edge cases to handle

Empty input. Single interval. All disjoint. All identical.

Complexity

O(n log n) sort + O(n) sweep.

Background lessons

• Sorting overview
• Arrays