Schedule exams so that each exam is assigned a day and no exam is held twice on the same day.
You are given a list of exam deadlines. For each exam, you must choose a day on which to take it. The chosen day cannot exceed that exam's deadline, and no two exams may be scheduled on the same day.
Find a valid schedule that maximizes the number of exams taken, or equivalently determine the best way to place exams into days so that the maximum number can be completed before their deadlines.
Input Format
- The first line contains an integer — the number of exams.
- The second line contains integers representing the deadlines of the exams.
Output Format
- Output the maximum number of exams that can be scheduled.
- If needed by the implementation variant, output one valid schedule achieving that maximum.
Constraints
- Deadlines are positive integers.
- Use an approach efficient enough for sorting-based greedy scheduling.
Example 1
Input
5 1 3 2 3 2
Output
4
Explanation
One optimal schedule is to take exams on days 1, 2, 3, and 4 with deadlines respected for four of the five exams. The remaining exam cannot be placed without conflicting with an already used day or missing its deadline.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.