시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 512 MB | 9 | 3 | 3 | 37.500% |
For all real numbers a ≤ b, the closed interval [a, b] refers to the set of all real numbers between a and b, inclusive. For example, [3, 5] = {x ∈ \(\mathbb{R}\) | 3 ≤ x ≤ 5}.
Bob has n closed intervals, denoted [a1, b1], [a2, b2], . . ., [an, bn], such that for all distinct i, j ∈ {1, 2, . . . , n},
He wants to color each of the n closed intervals monochromatically such that any two distinct overlapping intervals are in different colors. Bob wonders how many colors are needed. In other words, he wants to find the minimum positive integer k such that each of the n closed intervals can be labelled with one of 1, 2, . . ., k in a way that any two distinct overlapping intervals are labelled differently. Please help him.
The first line contains the number T of test cases. Each of the next T lines specifies a test case by providing n, a1, b1, a2, b2, . . ., an, bn, in that order. Two consecutive numbers in a line are separated by one or more spaces.
You may assume:
For each test case, output the minimum positive integer k such that each of [a1, b1], [a2, b2], . . ., [an, bn] can be labelled with one of 1, 2, . . ., k in a way that any two distinct overlapping intervals are labelled differently.
3 4 1 2 3 5 4 8 6 7 5 2 5 1 10 3 7 4 6 8 9 4 3 7 4 5 2 9 6 8
2 4 3
ICPC > Regionals > Asia Pacific > Taiwan > Taiwan Online Programming Contest > TOPC 2017 C번