Problem I
Room to Grow

A visual representation of the sample input.

In an old orchard there is an alley of trees. Unfortunately, at the pace the trees are growing, the alley will become overgrown and the trees will start dying due to a lack of light and competition for nutrients. The $i$th tree in the alley is positioned $d_ i$ metres from the end of the alley and has a radius $r_ i$ it is going to grow into. If there is no other tree within the radius, the tree will live, otherwise it will die. More precisely, if there is a tree at position $d_ j$ such that $d_ i - r_ i\leq d_ j \leq d_ i + r_ i$, then the tree at position $d_ i$ will die. It is clear that some trees need to be cut down to prevent trees from dying. What is the smallest number of trees to cut down in order for all remaining trees to have space to grow and not grow into other remaining trees?


The first line of input contains a single integer $n$, where $1\leq n \leq 5\, 000$, the initial number of trees. This is followed by $n$ lines each consisting of two space-separated integers $d_ i$ and $r_ i$, the distance along the alley of the $i$th tree and the radius required by the $i$th tree, respectively, where $1\leq d_ i \leq 1\, 000\, 000$ and $1\leq r_ i\leq 1\, 000\, 000$. No two trees are in the same position and the distance values are given in strictly increasing order.


Output a single integer, the smallest number of trees that need to be cut down to allow all remaining trees to grow.

Sample Input 1 Sample Output 1
1 3
5 2
7 2
9 3
15 4
18 1

Please log in to submit a solution to this problem

Log in