898. The Most Courses You Can Finish

n courses are offered. Course i takes t days of continuous study and must be FINISHED on or before day e. You start on day 0, study one course at a time with no gaps, and may skip any course.

Print the largest number of courses you can finish.

(100, 200) (200, 1300) (1000, 1250) (2000, 3200) -> 3 (5, 5) (5, 5) (5, 5) -> 1 (1, 2) (2, 3) (3, 4) -> 2

In the first example, take the 100-day course (finishing on day 100), then the 1000-day course (finishing on day 1100, before its limit of 1250), then the 200-day course (finishing on day 1300, exactly on its limit). The 2000-day course would push the total to 3300 and miss its own limit of 3200.

The second example has three identical courses of five days each with a limit of day 5, so only one can be finished.

## What most people try first

Taking the shortest courses first. On (1, 2) (2, 3) (3, 4) that gives 1 then 2, finishing at 3, which is fine, then 3 finishing at 6, which is not. Two courses, which happens to be right here. On other inputs it fails, because a short course with a tight limit is worth less than a longer one that enables more later.

Taking the courses with the earliest limits first. Also wrong on its own, for the same kind of reason: an early limit says nothing about how much time the course consumes.

Trying every subset. 2^n again.

## Why the order of study is forced

First, a fact that makes the whole problem tractable: if a SET of courses can be finished at all, it can be finished by studying them in increasing order of limit.

Take any feasible order in which some course x with a later limit runs immediately before a course y with an earlier limit. Swapping them leaves every other course untouched and leaves the pair finishing at the same total time. After the swap y finishes earlier than x did, and x finishes when the pair ends, which is when y finished before, and y's limit was the earlier one, so x is still inside its own limit. So the swap keeps feasibility. Repeating it sorts the set by limit.

So the ONLY question is which SET to take, and the order comes free.

## Sort by limit, then swap out the longest

sort the courses by limit ascending h = empty MAX-heap of durations clock = 0 for each course (t, e): push t; clock = clock + t if clock > e: clock = clock - pop(h) print size(h)

## Why swapping out the LONGEST is optimal

When the clock overshoots the current limit, exactly one course must go. Every course in the heap has a limit at or before the current one, so dropping any of them keeps the rest feasible. Since the count is what is being maximised, all courses are worth the same, and the only thing that distinguishes them is how much time they consume. Dropping the longest frees the most time for everything still to come, and it never reduces the count below what any other choice would allow.

Note that the dropped course may be the one just pushed, which is exactly what happens when a very long course arrives. The count then stays where it was and the clock returns to where it was, which is the correct outcome.

## The contrast with problem 897

Problem 897 has unit-time jobs and maximises PROFIT, so the resource is a day-slot, every accepted job consumes exactly one, and the discard rule is "drop the least valuable", a MIN-heap on profit.

Here every course is worth the same and the resource is TIME, consumed in different amounts, so the discard rule is "drop the most expensive", a MAX-heap on duration.

Same skeleton, opposite heap direction, for a reason that is visible in the objective. Getting that mapping right is the whole exercise.

## Overflow, with the actual magnitude

The clock is the trap. It accumulates durations of up to 10^9 and is compared against limits of up to 4 * 10^9, which is already outside a signed 32-bit integer whose ceiling is 2147483647. Reading a limit into a 32-bit type truncates it before any arithmetic happens.

The three-course test with durations 10^9 and limits 4 * 10^9 answers 3, and a 32-bit build answers 0.

## The boundary that breaks a careless implementation

A course whose own duration already exceeds its limit, such as (2, 1). It is pushed, the clock overshoots, and it is immediately the longest in the heap, so it pops straight back out. The code needs no special case for it, but a version that only pops when the heap has more than one entry hangs onto it.

## Cost

Time O(n log n). Space O(n).

Constraints - `1 ≤ n ≤ 200000` - `1 ≤ t ≤ 1000000000` - `1 ≤ e ≤ 4000000000`