Challenge: Most Talks in One Room

Lab Python Beginner 10 points

Read n talks with start and end times. Print the largest number of talks that can be held in one room without overlapping (a talk can start exactly when another ends). Use the greedy “earliest end first” rule.

Input

Line 1: n. Then n lines start end.

Output

One number.

Example

Input

Output

Sample input available Sample output available

Editor

Python

Hints

Sort the talks by end time.

Take a talk if it starts at or after the room becomes free.

Solution explanation

Finishing as early as possible always leaves at least as much room for the remaining talks.

Show solution

n = int(input())
talks = [tuple(map(int, input().split())) for _ in range(n)]
talks.sort(key=lambda t: t[1])
count = 0
free = -1
for s, e in talks:
    if s >= free:
        count += 1
        free = e
print(count)

Output

Answer