Merge overlapping intervals

Challenge

Given an array of interval_t { int start; int end; } (start <= end), merge overlapping intervals into a new array in place. Two intervals overlap if a.start <= b.end and b.start <= a.end (inclusive). Implement int merge_intervals(interval_t *intervals, int n). Mutates the input; returns the new (smaller or equal) count. Modifies the input array order.

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

n intervals, start <= end each. Up to 1000.

Output format

New length; first ret slots hold merged intervals (sorted by start).

Constraints

In place; use qsort.

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