Merge Overlapping Intervals

You are given a collection of intervals. Each interval is represented by two integers, the start and the end point. Your task is to merge all overlapping intervals and output a new list of intervals such that no two intervals overlap.

For example, if the input intervals are [[1, 3], [2, 6], [8, 10], [15, 18]], the merged intervals would be [[1, 6], [8, 10], [15, 18]].

You must read input from standard input (stdin) and write the result to standard output (stdout) in a Python-like list format.

inputFormat

The first line of input contains a single integer n which represents the number of intervals. The next n lines each contain two space-separated integers representing the start and end of an interval.

If n is 0, then there are no intervals.

outputFormat

Output a single line containing the merged intervals in the Python list format. Each interval should be represented as [start, end]. For example, if the merged intervals are [[1, 6], [8, 10], [15, 18]], then the output should be exactly:

[[1, 6], [8, 10], [15, 18]]

4
1 3
2 6
8 10
15 18

[[1, 6], [8, 10], [15, 18]]