Merge Overlapping Intervals

You are given a collection of intervals. Each interval is represented as a pair of integers \( [start, end] \). Your task is to merge all overlapping intervals and return a list of distinct intervals that cover all the intervals in the input.

An interval \( [a, b] \) overlaps with an interval \( [c, d] \) if \( c \leq b \) and \( a \leq d \). The resulting merged intervals should be sorted by their starting values.

For example, given intervals [1, 3] and [2, 6], the merged interval is [1, 6].

inputFormat

The first line of input contains a single integer \( n \) denoting the number of intervals. Each of the next \( n \) lines contains two space-separated integers representing the start and end of an interval.

\( \textbf{Constraints}: \)

• \( 0 \leq n \leq 10^5 \)
• \( -10^9 \leq start, end \leq 10^9 \)

outputFormat

Output the merged intervals, one per line. Each line should contain two space-separated integers representing the start and end of a merged interval. The intervals must be printed in increasing order of their start value.

0