line search?

[coolgod]

I was doing this usaco contest question which I was told it involved line searching.
the wikipedia article confused me.

Quote:

Problem 2: Soda Machine [Neal Wu, 2008]

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

As can be seen, the first, second and fourth cows share the point 5,
but the third cow's grazing range is disjoint. Thus, a maximum of
3 cows can have the soda machine within their grazing range.

PROBLEM NAME: soda

INPUT FORMAT:

* Line 1: A single integer: N

* Lines 2..N+1: Line i+1 contains two space-separated integers: A_i
and B_i

SAMPLE INPUT (file soda.in):

4
3 5
4 8
1 2
5 10

OUTPUT FORMAT:

* Line 1: A single integer representing the largest number of cows
whose grazing intervals can all contain the soda machine.

SAMPLE OUTPUT (file soda.out):

3

OUTPUT DETAILS:

If the soda machine is placed at location 5, cows 1, 2, and 4 can be
satisfied. It is impossible to satisfy all four cows.

If i understood line searching correctly, I basically skipped it with the c++ lower_bound method.
My program ran over the time.
I would like to learn more about this line search or techniques to do this question.
Any help?

[Tony]

The location of the machine will be at the right-side of some cow's edge (or left, by symmetry). If there exists a max answer such that it is not at the right-most edge of any cow, then the location can be moved one unit to the right, without putting it out of any cow's range. Thus, by induction, it could be moved to the right-sided edge of some cow.

This should get you going in the right direction of thought.

I propose an O(NlogN) solution, for N ~= 50,000