USACO

USACO 2024 December Contest, Gold

Problem 3. Job Completion

Contest has ended.

Log in to allow submissions in analysis mode

Bessie the cow has $N$ ( $1\le N\le 2\cdot 10^5$ ) jobs for you to potentially complete. The $i$ -th one, if you choose to complete it, must be started at or before time $s_i$ and takes $t_i$ time to complete ( $0\le s_i\le 10^{18}, 1\le t_i\le 10^{18}$ ).

What is the maximum number of jobs you can complete? Time starts at $0$ , and once you start a job you must work on it until it is complete, without starting any other jobs in the meantime.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains

$T$ , the number of independent test cases (

$1\le T\le 10$ ). Each test case is formatted as follows.

The first line contains $N$ .

Each of the next $N$ lines contains two integers $s_i$ and $t_i$ . Row $i+1$ has the details for the $i$ th job.

It is guaranteed that the sum of $N$ over all test cases does not exceed $3\cdot 10^5$ .

OUTPUT FORMAT (print output to the terminal / stdout):

For each test case, the maximum number of jobs you can complete, on a new line.

SAMPLE INPUT:

SAMPLE OUTPUT:

1
2
2

For the first test case, you can only complete one of the jobs. After completing one job, it will then be time $2$ or later, so it is too late to start the other job, which must be started at time $1$ or earlier.

For the second test case, you can start the second job at time $0$ and finish at time $2$ , then start the first job at time $2$ and finish at time $5$ .

SCORING:

Inputs 2: Within the same test case, all $t_i$ are equal.
Inputs 3-4: $N\le 2000$ , $s_i, t_i\le 2000$
Inputs 5-8: $N\le 2000$
Inputs 9-16: No additional constraints.

Problem credits: Benjamin Qi

Contest has ended. No further submissions allowed.