GATE CSE
First time here? Checkout the FAQ!
x
+5 votes
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
asked in Algorithms by Veteran (61.8k points)  
retagged by | 684 views

6 Answers

+15 votes
Best answer

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.

answered by Active (1.4k points)  
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
+5 votes

Answer: (B) 

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

Source: https://www.gatementor.com/viewtopic.php?f=267&t=2195

answered by Loyal (4.2k points)  
+1 vote
ans== 4 as we every new room is allocated when rest all allocated previously are filled
answered by (399 points)  
+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

answered by Junior (807 points)  
Could you please provide some reference for this solution ?
+1 vote

Total 4 rooms required. Option B is the answer.

answered by (349 points)  
0 votes
ans 4
answered by Boss (5.3k points)  
@Arjun Sir,

Is this a Activity Selection Problem ? Plz clear .
Answer:

Related questions



Top Users Aug 2017
  1. Bikram

    5272 Points

  2. ABKUNDAN

    4730 Points

  3. akash.dinkar12

    3514 Points

  4. manu00x

    3492 Points

  5. rahul sharma 5

    3188 Points

  6. makhdoom ghaya

    2700 Points

  7. just_bhavana

    2432 Points

  8. stblue

    2244 Points

  9. Tesla!

    2090 Points

  10. pawan kumarln

    1876 Points


25,071 questions
32,226 answers
75,102 comments
30,232 users