Job Completion
다이아몬드 IV의견: 0
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.
Problem credits: Benjamin Qi
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
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\).
For each test case, the maximum number of jobs you can complete, on a new line.
3
2
1 4
1 2
2
2 3
1 2
3
1 4
2 3
1 21
2
2For 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\).
riseoj 작성
출처 올림피아드 > USACO > 2024-2025 > December > Gold
평가 및 의견
Job Completion
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Job Completion