Activity Selection

Activity i runs from time starts[i] to time ends[i] (with starts[i] < ends[i]). You can attend only one activity at a time, and an activity that ends at time t does not overlap one that starts at t. Return the largest number of activities you can attend.

For starts = [1, 3, 0, 5, 8, 5] and ends = [2, 4, 6, 7, 9, 9] the answer is 4.

Examples

Example 1

Input:

max_activities([1, 3, 0, 5, 8, 5], [2, 4, 6, 7, 9, 9])

Output:

4

Example 2

Input:

max_activities([1, 2], [3, 4])

Output:

1

Constraints

• 0 <= len(starts) == len(ends) <= 200000
• 0 <= starts[i] < ends[i] <= 10**9