The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+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 (103k points)
recategorized | 610 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

by (155 points)

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
50,339 questions
55,765 answers
90,817 users