2.8k views

The following are the starting and ending times of activities $A, B, C, D, E, F, G$ and $H$ respectively in chronological order: $“a_s \: b_s \: c_s \: a_e \: d_s \: c_e \: e_s \: f_s \: b_e \: d_e \: g_s \: e_e \: f_e \: h_s \: g_e \: h_e”$. Here, $x_s$ denotes the starting time and $x_e$ denotes the ending time of activity X. We need to schedule the activities in a set of rooms available to us. An activity can be scheduled in a room only if the room is reserved for the activity for its entire duration. What is the minimum number of rooms required?

1. $3$
2. $4$
3. $5$
4. $6$
edited | 2.8k views

Solution: B

The problem can be modeled as a graph coloring problem. Construct a graph with one node corresponding to each activity $A,B,C,D,E,F,G$ and $H$. Connect the activities that occur between the start and end time of an activity. Now, the chromatic number of the graph is the number of rooms required.

edited
0
@aswlna i think so
0
How this graph is constructed?
+4
a very nice approach. :)

An alternative simpler approach i think which can be used here is the "maximum size of stack" which will be required at anytime of the computation, this will come out as 4.
0
Can you please share your complete approach how you are doing it by using stack?
+1
consider pushing each entry on start and pop the entry on end respectively....maximum size the stack grows during the procedure will be 4.
0
nice idea
+3

Though the stack method is much simpler, this is the how the graph is constructed :

asbscsaedsceesfsbedegseefehsgehe

Each distinct room is indicated by a distinct color.

1.Create a node for job A.

2.Job B which starts after A (and before A ends) should be given a different room. So we create a node for B and to ensure that A and B do not belong to the same room we give different color to these nodes. If we connect A and B then we can ensure that the chromatic no. of the graph (till now) will give us the no. of different rooms.

3. Job C has arrived while A and B are still in execution. This means a 3rd room has to be given to C. How can we ensure that using colors? If we connect A and B both to C then the chromatic no. becomes 3 which again indicates the no. of different rooms needed till now.

4. A ends. D starts. So we can give the room left by A to D. Then we don't connect A and D in the graph so that they can get the same color. BUT we have to connect D with B and C because their color (rooms) can't be given to D.

5. C ends. E starts. Currently D and B are still in execution occupying 2 different rooms. So E can't get their colors. Connect D and B to E.

6. F starts. B,D,E are still there. So connect F with B,D,E.

7. B ends. D ends. E and F are still there. G starts. Connect G to E and F.

8. E ends. F ends. G is still there. H starts. Connect H to G.

0
No its not.
0
Same as working set algo in OS. Max frame requirement at any time t.
0
Both ways of solving this problem are great, but the approach using stack is quick.

Explanation: Room1 – As
Room2 – Bs
Room3 – As
now A ends (Ae) and now Room3 is free
Room3-Ds
now A ends (Ae) and Room1 is free
Room1-Es
Room4-Fs
now B ends Room2 is free
now D ends Room3 is free
Room2-Gs
now E ends Room1 free
now F ends Room4 free
Room1-Hs
now G and H ends.
Totally used 4 rooms

We need "minimum" 4 room to accommodate all activities A to H as per conditions

Total 4 rooms required. Option B is the answer.

0
best explaination
ans== 4 as we every new room is allocated when rest all allocated previously are filled

This type of problem can be solved by array representation of starting time  ( taking +1) and ending time (taking -1 )

 +1 +1 +1 -1 +1 -1 +1 +1 -1 -1 -1 -1 -1 -1 -1 -1

now taking sequence from array and sum  them for getting largest positive no

 +1 +1 +1 -1 +1 -1 +1 +1

this array is 1st 8 sequences of original array and sum is 1+1+1-1+1-1+1+1=4

so ans is 4

0

Could you please provide some reference for this solution ?

+1 vote
This question is similar to the question where arrival and departure time of trains are given and we have to calculate minimum no of platforms required. The logic is whenever job start/train comes cont++ when depart/end counnt-- then the maxm value of count in bw will be the ans.Note at the end count=0

eg .      as, bs be,cs,ce,ae

count: 1.   2 .   1 . 2.  1 .0

maxm value of count is 2 so two platforms/room req.
0
Nice approach
Easiest way is, just start a counter initialised to 0, now start traversing the time stamps array if the current time is  a start time add 1 to the counter and if the current time is end time subtract 1 from counter, the max value attained by the counter in the process is the answer.

Applying the logic on the given order give answer as B ie 4.
–1 vote
ans 4
0
@Arjun Sir,

Is this a Activity Selection Problem ? Plz clear .
+1
this is a copy paste question from CLRS book,read the question here,I think the graph is wrong is wrong I think we need to link all incompatible activities,i.e activities which overlaps one another and then find chromatic no.

Page 422 chapter 16.

16.1-4
Suppose that we have a set of activities to schedule among a large number of lecture
halls, where any activity can take place in any lecture hall. We wish to schedule
all the activities using as few lecture halls as possible. Give an efficient greedy
algorithm to determine which activity should use which lecture hall.
(This problem is also known as the interval-graph coloring problem. We can
create an interval graph whose vertices are the given activities and whose edges
connect incompatible activities. The smallest number of colors required to color
every vertex so that no two adjacent vertices have the same color corresponds to
finding the fewest lecture halls needed to schedule all of the given activities.)
0
once you understand this question its pretty simple

starting from a timestamp say 0.

As (A starts at 1 ),Bs(B starts at 2) ,Cs(C starts at 3),Ae(A finishes at 4) and so on..

1
2