Merge Overlapping Intervals

Problem Description:

You are given a list of intervals for each test case. Your task is to merge all overlapping intervals and return the list of disjoint intervals such that they cover all the intervals in the input. Two intervals overlap if the end time of one is greater than or equal to the start time of the other.

Note: The expected time complexity is \(O(n \log n)\) due to the sorting step required.

Example:

Input:
1
3
1 3
2 6
8 10
Output:
2
1 6
8 10

inputFormat

The input begins with an integer (T) representing the number of test cases. For each test case, the first line contains an integer (N), the number of intervals. The following (N) lines each contain two space-separated integers, representing the start and end of an interval.

outputFormat

For each test case, first output an integer representing the number of merged intervals. Then, for each merged interval, print its start and end values separated by a space on a new line.## sample

1
3
1 3
2 6
8 10

2
1 6
8 10