Choose the largest subset of movie showings that can be watched back-to-back without overlap.
Watching a Movie
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 — the number of movie showings.
- The next lines each contain two integers and , representing the start and finish time of the -th showing.
Output Format
- Print one integer: the maximum number of movies that can be watched one after another without overlap.
Constraints
- Times are integers.
- A movie ending at time allows another movie starting at time or later.
- Exact official limits are unknown from the provided metadata.
Example 1
Input
3 1 3 2 5 4 6
Output
2
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.