Problems Base course RU

How many by the deadline

scheduling greedy heap sorting classic contests

A print shop has one press and n orders. Order i occupies the press for p_i hours in a row and is promised by hour d_i, counting from the start of work. The press starts at time 0 and does the orders one at a time without breaks, in an order the shop chooses. An order is on time if it is finished no later than its deadline; a late order is still done, but later, and how late it is does not matter.

What is the largest number of orders that can be done on time?

Input

The first line holds the number of orders n (1 ≤ n ≤ 10⁵). Then n lines “p_i d_i”: 1 ≤ p_i ≤ 10⁶, 1 ≤ d_i ≤ 10¹¹.

Output

One number: the largest number of orders done on time.

The first example is the eight orders from the article: seven can be done on time if the posters are left to the end. In the second, the five-hour order can be done on time, but then two of the three one-hour orders are late, while if it is put off, all three make it.

Examples

Example 1

Input

Output

Example 2

Input

Output

Limits

Time · Python: 3000 ms
Time · Go: 1000 ms
Memory: 256 MB
Judging: 11 tests

Walkthrough

Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.

1Hint 1

Suppose it is already decided which orders to do on time. In what order should they be run to check that all make it? And if in this order some order is late, which of those already taken is it best to give up?

2The idea

A set of orders can be done on time if and only if the deadline order manages it: this is Jackson’s rule from the article on greedy algorithms; if the largest lateness in deadline order is zero, it is zero, and nothing is less. So go through the orders by deadline and collect them. As soon as the next order is late, someone among those taken, including itself, must go: together they do not fit before its deadline. The longest goes: it frees the most time, and everything taken fits again. Why this is no worse than any other choice is proved in the article: the exchange “instead of any discarded order, discard the longest” spoils nothing.

3Walkthrough

Sort the orders by deadline. Keep the sum of hours of the orders taken, t, and a heap of their durations with the largest on top. Take the next order: push its duration onto the heap and add it to t. If t exceeded this order’s deadline, pop the largest duration from the heap and subtract it from t. One removal is enough: the longest is no shorter than the one just taken, and without the new order everything fitted. At the end the size of the heap is the answer.

The sum of durations reaches 10¹¹: in Go a 64-bit int is needed.

3+Solution

4Complexity

O(n log n): a sort and at most two heap operations per order.

5Common mistakes

Taking an order only if it fits. Then on a late order the new order is discarded rather than the longest. The second example: the five-hour order stays, and the three one-hour ones are lost.
Shortest first. Ordering by duration ignores the deadlines and loses already on the first example.
Forgetting to subtract. A discarded order goes to the end and no longer occupies the press before the others’ deadlines; if its hours are not subtracted from t, the following orders will be late for nothing.

Algorithms behind it

SYS Algorithm Scheduling The order of work: shortest first, deadlines, preemption, many cores and Graham’s anomalies. O(n log n): a sort or a heap 2 problems PAR Technique Greedy algorithms The best step now with no looking back: when it is optimal, when almost, and how to prove it. usually O(n log n): a sort or a heap 2 problems DS Data structure Binary heap The minimum at hand, insertion and extraction in O(log n): the tree in an array that event calendars live on. O(log n) 2 problems