Problem 1. Consider the following scheduling problem. Let S be a set of n activities. An activity i is given as a time interval (si , fi). Two activities can be assigned to the same room if their time intervals do not overlap. The task is to find an assignment of all activities to rooms using minimum number of rooms.

(b) Algorithm B (greedy-by-time): Initially R = . Process the activities in increasing order of start times. If the current activity can be assigned to one of the rooms in R, then assign it to any such room; otherwise assign it to a new room and add this room to R. Does Algorithm B always solve the scheduling problem? Justify your answer.