Schedule as many exams as possible before their deadlines, choosing an order that maximizes the count.
You are given a set of exams. Each exam takes one day to complete and has a deadline by which it must be finished. Starting from day 1, you may take at most one exam per day.
Your task is to choose a subset of exams and an order to take them so that every chosen exam is completed no later than its deadline, while the total number of completed exams is as large as possible.
Return the maximum number of exams that can be passed.
Input Format
- The first line contains an integer — the number of exams.
- The next lines contain two integers and describing the -th exam.
- is the earliest day you can start preparing or taking the exam if needed in the original problem wording, and/or the first relevant time value.
- is the deadline / last possible day associated with the exam.
Note: This is a prep-oriented rephrasing of the classic scheduling problem; interpret the pair as a deadline-based exam scheduling constraint.
Output Format
Print one integer — the maximum number of exams that can be completed on time.
Constraints
- Time values fit in 32-bit signed integers
- An exam takes one day, and at most one exam can be handled per day
Example 1
Input
3 3 5 1 2 2 4
Output
2
Explanation
One optimal plan is to complete the exam with deadline 2 on day 1 and the exam with deadline 4 on day 2. The exam with deadline 5 can still be skipped, so the maximum count is 2.
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.