Flight Packet Deadline Desk
Maximum tasks completed by deadlines from duration-deadline pairs
An airport has one desk that prepares clearance packets for departing flights. All packets are available at time 0.
Each row flights[i] = [duration, deadline] describes a packet that takes duration minutes to prepare and must be finished no later than deadline minutes after time 0.
The desk can prepare at most one packet at a time. Once preparation starts, it must continue uninterrupted until that packet is finished. Packets may be prepared in any order, and any packets may be skipped. Finishing exactly at a deadline is allowed.
Return the maximum number of packets the desk can finish by their respective deadlines.
Examples
Example 1
Input: flights = [[5,5],[2,6],[3,7]] Output: 2
Preparing the second packet before the third meets both deadlines. Including the first packet as well makes it impossible to meet every selected deadline.
Example 2
Input: flights = [[8,3],[2,2],[2,4],[1,5]] Output: 3
The first packet cannot meet its deadline even if it starts immediately. The other packets can be prepared consecutively in deadline order.
Example 3
Input: flights = [] Output: 0
No packets are waiting, so there is no preparation work to schedule.
Constraints
- 0 <= flights.length <= 4000
- Each flights[i] contains exactly two integers: duration and deadline.
- 1 <= duration <= 1000000000
- 1 <= deadline <= 1000000000
The intended solution takes O(n log n) time and O(n) auxiliary space. Rows need not be supplied in deadline order, and duplicate rows represent separate packets.
Hints
Show hint 1Hint 1
For any chosen set of packets, consider preparing them in increasing deadline order.
Show hint 2Hint 2
When a newly considered packet makes the retained set take too long, which single packet should you remove to leave the most room for future packets?
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you return one optimal set of original packet indices instead of just its size?
- Does the same rule remain correct if packets have different rewards and the goal is to maximize total reward?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem