Exams · Interview Problem

Back to problems

Codeforces

Medium

Arrays

Sorting

Greedy

Google

Exams

Schedule as many exams as possible before their deadlines, choosing an order that maximizes the count.

Acceptance 0%

Start Practice

Problem Statement

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 $n$ — the number of exams.
The next $n$ $n$ lines contain two integers $a_i$ $a_{i}$ and $b_i$ $b_{i}$ describing the $i$ $i$ -th exam.
- $a_i$ 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.
- $b_i$ 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

$1 \le n \le 2 \cdot 10^5$
Time values fit in 32-bit signed integers
An exam takes one day, and at most one exam can be handled per day

Examples

Sample cases returned by the problem API.

Example 1

Input

Output

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.

Guided hints

Editorial and discussion links

Concept map and variants

Track your progress