2.3k 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.3k 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
@Arjun Sir is given solution correct??
0
yes that is logical, why there is a confusion?
0
sir chromatic num ! is 4 here??
+1
@Arjun sir...by 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..
+2
For b-d-e-f we need minimum 4 colors rt?

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

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

0
Can you please explain how graph is constructed
+1
@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
+1
@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.
+9
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.
0
@Arjun Sir,

Is this a Activity Selection Problem ? Plz clear .
0
@aswlna i think so
0
How this graph is constructed?
+3
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
+2

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.

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.

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 ?

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

1
2