To meet the ever-growing demands of his N (1 <= N <= 50,000) cows,
Farmer John has bought them a new soda machine. He wants to figure
out the perfect place to install the machine.
The field in which the cows graze can be represented as a one-dimensional
number line. Cow i grazes in the range A_i..B_i (1 <= A_i <= B_i;
A_i <= B_i <= 1,000,000,000) (a range that includes its endpoints),
and FJ can place the soda machine at any integer point in the range
1..1,000,000,000. Since cows are extremely lazy and try to move
as little as possible, each cow would like to have the soda machine
installed within her grazing range.
Sadly, it is not always possible to satisfy every cow's desires.
Thus FJ would like to know the largest number of cows that can be
satisfied.
To demonstrate the issue, consider four cows with grazing ranges
3..5, 4..8, 1..2, and 5..10; below is a schematic of their grazing
ranges:
1 2 3 4 5 6 7 8 9 10 11 12 13 |---|---|---|---|---|---|---|---|---|---|---|---|-... aaaaaaaaa bbbbbbbbbbbbbbbbb ccccc ddddddddddddddddddddd
There are multiple test cases in the input file.
* Line 1: A single integer: N
* Lines 2..N+1: Line i+1 contains two space-separated integers: A_i
and B_i
4 3 5 4 8 1 2 5 10 4 3 5 4 8 1 2 5 10
3 3
Migrated from old NTUJ.
USACO QUAL10
No. | Testdata Range | Score |
---|