All problems

Most Talks Attended

Medium · greedy

A conference runs many talks. Each item [start, end] of talks is a talk that begins at minute start and finishes at minute end.

You can only be in one talk at a time, and once you walk in you stay until it ends. A talk that ends at minute t and another that starts at minute t can both be attended, because you can walk straight from one to the other. Any two talks that share some stretch of time cannot both be attended.

Return the largest number of talks you can attend. The talks come in no particular order.

Examples

Example 1

Input: talks = [[9, 12], [9, 10], [10, 11], [11, 13]]

Output: 3

Attend [9, 10], then [10, 11], then [11, 13]. The long talk [9, 12] would block all of them.

Example 2

Input: talks = [[1, 5], [2, 6], [3, 7]]

Output: 1

Every pair of talks overlaps, so you can attend only one of them.

Example 3

Input: talks = [[0, 100], [10, 20], [20, 30], [30, 40]]

Output: 3

Skip the all-day talk and attend the three short ones, which touch end to start.

Constraints