Tessellate S.T.E.M.S - Computer Science - School - Set 2 - Problem 3

We have $n$ events each of them characterized by their starting time and ending time $(a_i, b_i)$ with $(a_i <= b_i)$

Let $S$ be a set containing all these events.

Now lets consider a algorithm

• Keep doing the following steps until $S$ is empty:
• Step 1: you choose the event ending the earliest in set $S$
• Step 2: now delete all the events in $S$ having a intersection with this chosen event then go to step one

Let $g =$ the number of times you did step 1, $p =$ the maximum number of events which can be chosen such that none of them intersect with each other

Two event $(x_1,y_1)$ and $(x_2,y_2)$ with $(x_1 \leq y_1 )$ and $(x_2 <= y_2)$ don't intersect if $x_1 >y_2$ or $x_2 > y_1$ .

---

This problem is a part of Tessellate S.T.E.M.S.