Most Orders by Their Deadlines

Hard

A freelancer is offered several orders. Order orders[i] = [days, deadline] takes days days of continuous work and must be delivered no later than the end of day deadline. Work starts on day 1, only one order can be in progress at a time, and an order, once started, is worked on without breaks until it is done. Orders may be taken in any sequence, and any of them may be declined. Return the maximum number of orders the freelancer can deliver on time.

Example 1

orders=[[3, 5], [4, 6], [2, 7], [5, 12]] → 3

For instance: order [3, 5] on days 1–3, [2, 7] on days 4–5, [5, 12] on days 6–10. All four cannot fit: the first three together take 9 days, but the last of them is due by day 7.

Example 2

orders=[[6, 4], [5, 3]] → 0

Each order takes longer than its deadline allows, so none can be taken.

Example 3

orders=[[2, 2], [2, 4], [2, 6]] → 3

Constraints

1 ≤ len(orders) ≤ 10⁴
1 ≤ days, deadline ≤ 10⁴

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Array Sorting Heap (Priority Queue)

Similar problems

Growing Capital Project by Project Hard Narrowest Range Touching Every List Hard Crew Paid by Skill Hard The Slowest Sets the Squad's Pace Hard Score Spread of Parcel Groups Hard

Input

orders=[[3, 5], [4, 6], [2, 7], [5, 12]]

Expected

Run checks the first 3 tests in your browser. Submit checks all 132 tests on the server, hidden ones included.