A single machine runs tasks in unit-length time slots numbered 1, 2, 3, ... (one task per slot, starting at slot 1). There are n tasks, and task i has an integer deadline d[i] ≥ 1, meaning it must be placed in a slot no later than d[i] (a task placed in slot t finishes at time t).
Decide whether there is an assignment of the n tasks to distinct slots so that every task finishes by its own deadline.
Line 1: an integer n.
Line 2: n space-separated integers, the task deadlines.
Print YES if all tasks can be scheduled to meet their deadlines, otherwise print NO.
Example 1
Input
3 1 2 3
Expected
YES
Explanation
Sorted deadlines 1,2,3. Slot 1 needs deadline ≥ 1, slot 2 needs ≥ 2, slot 3 needs ≥ 3 — all satisfied: YES.
Example 2
Input
3 2 1 1
Expected
NO
Explanation
Sorted deadlines 1,1,2. The second slot needs a deadline ≥ 2 but only a deadline-1 task remains there, so it is impossible: NO.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →