674 views

In Activity-Selection problem, each activity $i$ has a start time $s_i$ and a finish time $f_i$ where $s_i \leq f_i$. Activities $i$ and $j$ are compatible if

1. $s_i \geq f_j$
2. $s_j \geq f_i$
3. $s_i \geq f_j$ or $s_j \geq f_i$
4. $s_i \geq f_j$ and $s_j \geq f_i$

recategorized | 674 views

Two activities are compatible if they can be completed in some order and don't overlap in time. To complete two activities, START time of one activity must be greater than or equal to FINISH time of other activity i.e one activity must start only after other finishes. So,

Si >= Fj or Sj >= Fi