In Activity-Selection problem, each activity \(π\) has a start time \(π _π\)β¦
2015
In Activity-Selection problem, each activityΒ \(π\)Β has a start timeΒ \(π _π\)Β and a finish timeΒ \(π_π\)Β whereΒ \(π _π β€ π_π\). ActivitiesΒ \(π\) andΒ \(π\)Β are compatible if :
- A.
\(s_i \geq f_j\) - B.
\(s_j \geq f_i\) - C.
\(s_i \geq f_j \ or \ s_j \geq f_i\) - D.
\(s_i \geq f_j \ and \ s_j \geq f_i\)
Attempted by 235 students.
Show answer & explanation
Correct answer: C
Answer: Two activities i and j are compatible if one finishes before (or at) the other starts, i.e., s_i β₯ f_j or s_j β₯ f_i.
Explanation:
Compatibility means the time intervals for the activities do not overlap.
If s_i β₯ f_j, activity i starts at or after activity j finishes, so they do not overlap.
If s_j β₯ f_i, activity j starts at or after activity i finishes, so they do not overlap.
Either of these non-overlapping scenarios is sufficient, so the correct relation uses a logical OR.
Requiring both inequalities at once is unnecessarily strict and only possible in degenerate cases (for example, zero-length activities), so the AND form is incorrect for general compatibility.
Example: Activity A with times [1,3] and activity B with times [3,5] are compatible because the start of B equals the finish of A (s_B = f_A).