684 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
retagged | 684 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.

selected by
@rajesh draw a horizontal time line and mark the time positions,here each pair is a edge between vertex a and b, i think the time line method is better

all those guys having confusion can also check register allocation problem solution by using graph colouring, the soltion is similar
@Abhinav93 Graph is constructed as follows, when a starts inside it's room there are b,c therfore edge is there between (a,b) (a,c) simillarly when room is available for "b" inside when it get finish the room also have (a,c,d,e,f) as follows, hope you understand.
Simple Way:

For each time unit make a stack . for "s" operation insert into the stack and for "e" operation delete from the stack . Think That you can delete an element from any position of the stack. Maximum height at a particular instance of time is the answer.
@Arjun Sir,

Is this a Activity Selection Problem ? Plz clear .
@aswlna i think so

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

+1 vote
ans== 4 as we every new room is allocated when rest all allocated previously are filled
+1 vote

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

Could you please provide some reference for this solution ?
+1 vote

Total 4 rooms required. Option B is the answer.

ans 4
@Arjun Sir,

Is this a Activity Selection Problem ? Plz clear .