Activity Selection - Classic Problems | Repovive

CLS51. Activity Selection

2s256 MB

Given $n$ half-open intervals $[l_i, r_i)$ , choose the maximum number of intervals so that no two chosen intervals overlap.

\begin{array}{l} n \\ l_1 \quad r_1 \\ l_2 \quad r_2 \\ \vdots \\ l_n \quad r_n \end{array}

count_{\max}

Input

Explanation

Choosing [1,3), [3,6), and [6,8) gives 3 non-overlapping intervals.

Output

Input

Explanation

The intervals [1,2) and [2,3) can both be chosen, so the answer is 2.

Output

Input

Explanation

One maximum choice is [2,3), [3,5), and [7,9), giving 3.

Output

Given $n$ half-open intervals $[l_i, r_i)$ , choose the maximum number of intervals so that no two chosen intervals overlap.

\begin{array}{l} n \\ l_1 \quad r_1 \\ l_2 \quad r_2 \\ \vdots \\ l_n \quad r_n \end{array}

count_{\max}