Boats
InterviewTime limit1sMemory limit512 MB
Each boat has a fixed length and an assigned ring position; tie a boat so its ring falls anywhere on the boat, boats may touch but not overlap. Maximize the number of boats tied.
- Level
Medium7 of 10
- Topics
- Greedy, Sorting, Intervals, Dynamic programming
- Solved
- No attempts yet
Problem
Magicians are coming to the great assembly of Aglargond School of Magic. They can travel by boat, among other means. The organizers reserved one ring for each participant, so each magician can tie his boat to the ring assigned to him. Every magician sent the length of his boat to the organizers. A boat must be tied so that the ring lies somewhere along the length of the boat, endpoints included. Boat ends may touch, but boats cannot overlap (see the picture). Because of this restriction, it may be impossible to tie all boats at the same time. The organizing committee of the Magician Assembly asks you to write a program that finds the maximum number of boats that can be tied at the same time to their assigned rings.
| Allowed | Not allowed |
|---|---|
 |  |
Input
The first line contains the number of magicians, N (1 ≤ N ≤ 10000). Each of the following N lines contains two space-separated integers li and pi (1 ≤ li, pi ≤ 100000, 1 ≤ i ≤ N): the length of the boat and the position of the assigned ring measured along the river bank from the school building. No two rings have the same position.
Output
Print one line with a single number: the maximum number of boats.