The Gateway to Computer Science Excellence
+4 votes

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$
in Algorithms by Veteran
recategorized | 674 views

1 Answer

0 votes

Answer is C

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


Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,223 questions
59,811 answers
118,087 users