Now that we have seen quick-sort and implemented it, it’s time to solve a challenging problem using quick-sort. You can work in any programming language of your choice - Python, C++, Java, or anything else you want. Let’s get started!

Problem Statement

We’re given $n$ intervals, and our task is to calculate if any two given intervals overlap. Each interval is simply a range described by two integers $(s, e)$. Both $s$ and $e$ are included in the interval. For example, (3, 5) overlaps with (5, 6) as well as with (2, 8). But it does not overlap with (1, 2) or (8, 12).

Constraints: $n \leq 500000$. Desired solution has complexity O($n \log n$). For each interval $(s, e)$, we have $s \leq e$.

IO description

Input description: The first line contains the number of test cases T. Each test case consists of two lines. The first line has a single number $n$, denoting the number of intervals. The second line has a list of $n$ intervals separated by commas (", ").

Sample Input:

3
3
1 3, 6 7, 4 6
3
1 3, 7 7, 4 6
3
1 3, 4 7, 5 6

Output description: Output should contain T lines. Each line should contain the answer for the respective test case - YES if at-least one pair of intervals overlap, and NO if no pair of intervals overlap.

Sample output:

YES
NO
YES

Explanation:

In the first test case, (4, 6) overlaps with (6, 7).

In the second test case, no pair of intervals overlap.

In the third test case, (4, 7) overlaps with (5, 6).

Submitting your solution

Once you are confidant of your solution, download the input file and run your code with the provided input. Then take the quiz!

Progressive ‘hint-by-hint’ solution

Only look at the hints if you can’t solve the problem for at-least 20-minutes. Read only one hint that you could not figure out on your own. Then spend at-least 20-minutes trying to solve the problem again.

Hint 1:

Comparing every pair of intervals is too slow. What can we do to improve the solution?

Hint 2:

Suppose we sort all intervals by their start locations $s$. If there are overlapping intervals, where must they be?

Full solution

The solution for this assignment is included at the end of the quiz. The code executes in ~3 seconds. If you implemented your solution in C++ or Java, you should expect your solution to run at-least 5x faster.