Watching a movie

Back to problems

Codeforces

Easy

Arrays

Math

Watching a movie

Choose the largest subset of movie showings that can be watched back-to-back without overlap.

Acceptance 0%

Start Practice

Problem Statement

You are given the start and finish times of several movie showings. You want to watch as many movies as possible, but you can only watch one movie at a time.

A movie can be watched if it starts at or after the time you finish the previous one. Your task is to determine the maximum number of movies you can watch by choosing an optimal order of showings.

This is a classic scheduling problem: pick showings so that each chosen movie finishes as early as possible while still being compatible with the next one.

Input Format

The first line contains an integer $n$ — the number of movie showings.
The next $n$ lines each contain two integers $a_i$ and $b_i$ , representing the start and finish time of the $i$ -th showing.

Output Format

Print one integer: the maximum number of movies that can be watched one after another without overlap.

Constraints

$1 \le n$
Times are integers.
A movie ending at time $t$ allows another movie starting at time $t$ or later.
Exact official limits are unknown from the provided metadata.

Examples

Sample cases returned by the problem API.

Example 1

Input

Output

Explanation

Watch the movie from 1 to 3, then the movie from 4 to 6. The middle movie overlaps with the first choice.

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