Question 6920 – UGC NET CS 2015 Dec – paper-3

Each activity a_i has a start time s_i and a finish time f_i where 0 ≤ s_i < f_i < ∞. If selected, activity a_i takes place during the half-open time interval [ s_i , f_i ]. Activities a_i and a_j are compatible if the intervals [ s_i , f_i ] and [ s_j , f_j ] do not overlap. That is, a_i and a_j are compatible if s_i ≥ f_j or s_j ≥ f_i. In the activity-selection problem, we wish to select a maximum-size subset of mutually compatible activities.