Light it up
Practice
4.2 (18 votes)
Hard
Problem
50% Success 204 Attempts 50 Points 1s Time Limit 256MB Memory 1024 KB Max Code

There are N buildings placed on the line Y = 0. Each building can be considered as rectangle described by 3 integers Li, Ri, Hi with corners (Li; 0); (Ri; 0), (Li; Hi), (Ri; Hi) .

You can place any number of lights on the roof of any building at any point (i.e. at any point of any segment (Li; Hi) - (Ri; Hi) ). Your goal is to make all the side walls completely illuminated.

The point is considered as illuminated by some light source if the segment connecting the light source and the point contains no internal points of the buildings (but it can contain edge points).

What is the minimum number of lights you have to place to achieve your goal?

Input

The first line contains one integer T denoting the number of test cases.

Each of the following T test cases starts with the line containing one integer N - the number of building. The followng N lines contain 3 integers Li, Ri, Hi each.

It's guaranteed that buildings don't intersect or touch each other.

Output

For each test case output one integer on a separate line - the answer for this test.

Constraints

  • 1 <= N <= 1000
  • sum of squared values of N over all test cases doesn't exceed 1 000 000 in each test file.
  • 0 < Li, Ri, Hi <= 10 000
  • Li < Ri

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:30
4 votes
Tags:
Medium
Points:30
11 votes
Tags:
AlgorithmsBinary SearchEasySearching
Points:30
1 votes
Tags:
CombinatoricsDynamic ProgrammingMediumCRT