The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+21 votes

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 (59.4k points)
retagged by | 1.7k views

7 Answers

+27 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)
edited by
@Arjun Sir is given solution correct??
yes that is logical, why there is a confusion?
sir chromatic num ! is 4 here??
@Arjun simply i'm getting the ans...I  have check only no of Xs but doesn't contain Xe between Ys And Ye...which one gives max is the ans..

Here Bs,Ds,Es,Fs are the rooms... so max =4

a'm i rt??

but by graph i'm not getting..
For b-d-e-f we need minimum 4 colors rt?

And yes, you can do like that- graph making is just another way.
How have you made the connections....can you explain more .
ok..I got it

according to above concept ,how will we create a graph here and their connections ?plss help 

Can you please explain how graph is constructed
@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
How this graph is constructed?
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.
Can you please share your complete approach how you are doing it by using stack?
consider pushing each entry on start and pop the entry on end respectively....maximum size the stack grows during the procedure will be 4.
+9 votes

Answer: (B) 

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


answered by Active (4.6k points)
+4 votes

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

answered by Loyal (7.7k points)
+2 votes
ans== 4 as we every new room is allocated when rest all allocated previously are filled
answered by (411 points)
+2 votes

 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 Active (2.2k points)

@Gate Ranker18,

Could you please provide some reference for this solution ?

+2 votes

Total 4 rooms required. Option B is the answer.

answered by Active (1.8k points)
–1 vote
ans 4
answered by Active (5.2k points)
@Arjun Sir,

Is this a Activity Selection Problem ? Plz clear .
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.

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.)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

35,506 questions
42,827 answers
42,181 users