Touching Segments

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 1.4s
Java 3.5s
Memory limit: 256M

Problem type

Your Maths professor is a very nice guy, but he sometimes comes up with not-so-funny tasks. Today is one such day. The professor drew a bunch of parallel line segments on the board and asked the following question: "How many of these segments can be touched, even on their edges, by exactly two lines perpendicular to them?"

After a few seconds, he spoke again: "Let's make it more interesting. I will give you the starting and the ending points of N segments over the X's axis; today's homework will be to answer the question I asked you above for any set of such segments". Right after the professor's words, one guy asked: "Is there any restriction over the segments' location?", and the professor replied: "Not really, they are just segments, so they can overlap in all the ways you may imagine."

Everybody started thinking of the weird and unexpected task, without getting a convincing result. Some time later, the class got over and before leaving the classroom, the professor said: "Just to take this to the ultimate limits, your final qualification will depend entirely on this task. Good luck and please, don't try to cheat, I will know if you try to do so." So, that was it! Your final Maths qualification was hooked to some play on segments stuff.

Input Specification

Input consists of several test cases. The first line in the input is an integer, T, denoting the number of test cases. T test cases follow, each one with the following format:

  • A single line with an integer, N, denoting the number of segments.
  • N lines, each defining a segment with two integers, a and b, separated by a single white space, meaning that there is a segment going from a to b.


1 \le T \le 5
1 \le N \le 10^5
0 \le a < b \le 10^9

Output Specification

For each test case the output should follow the following format:

  • A single line with Case #: answer where # is the serial number of the current test case (start the numbering from 1) and answer is the maximum number of segments you can touch as described above.

See the sample output for more details.

Sample Input

2 3
1 3
1 5
3 4
4 5
1 2
1 3
2 3
1 4
1 5
1 5
1 6
1 7
8 10
1 2
3 4
5 6

Sample Output

Case 1: 5
Case 2: 5
Case 3: 4
Case 4: 2

Explanation of Output for Sample Input

  • Case 1: We will draw two lines (parallel to Y-axis) crossing X-axis at points 2 and 4. These two lines will touch all five segments.
  • Case 2: We can touch all the points even with one line crossing X-axis at 2.
  • Case 3: We will draw the first line at any point in range [1,5] so that it can touch the first three lines. We will draw the second line crossing X-axis at any of the points in range [8,10] and it will touch the last line.
  • Case 4: It is not possible to touch more than two lines in this case.

Original Problem Author: shaka_shadows; Problem Resource: HackerRank


There are no comments at the moment.