GATE CSE 2003 | Question: 69

Question

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?

• A. $3$
• B. $4$
• C. $5$
• D. $6$

Comments

Option (B) is correct, Here we can follow below steps

---

We can select non-overlapping activities in increasing order of their time duration. i.e we are greedily selecting activity with least time duration first.

---

Simple one. Think like this:

Let the set of activities given are the trains arriving to a particular station, with N no. of platforms.So Xs and Xe will be the train arrival times and train departure times.

So ATQ, we have to find out the value of N so that all stations can arrive and depart at their scheduled times.

 As maximum 4 trains present at a time, we need atleast N = 4 platforms to accumulate all the trains so that they can arrive and depart freely at their scheduled time.

Thats it, now referring to the question, atleast 4 rooms needed to carry out the set of activities. 

Answer 1

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.

Comments

@Arjun Sir is given solution correct??

---

yes that is logical, why there is a confusion?

---

sir chromatic num ! is 4 here??

---

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

---

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.

---

nice idea

---

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

“a_sb_sc_sa_ed_sc_ee_sf_sb_ed_eg_se_ef_eh_sg_eh_e”

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.

---

No its not.

---

Same as working set algo in OS. Max frame requirement at any time t.

---

Both ways of solving this problem are great, but the approach using stack is quick.

---

just, think like stack items, then we can get answer fast

---

Very intutive

---

This is innovative approach but constructing the graph itself by looking at the starting time & ending time of an activity on the screen itself takes more 2-3 minutes,not suitable in exam

---

Could u tell me what made u think in the first place to start off this problem with graph coloring problem ?

---

It is interval partitioning problem and there is a polynomial-time algorithm for it. Finding chromatic number is not an easy problem. It is NPC problem and sometimes can give wrong answer for small graph also but using chromatic partitioning, one can get the correct answer but it is time taking.

According to one theorem, "In any instance of Interval Partitioning, the number of resources needed is at least the depth of the set of intervals." Proof is also very easy.

So, here, activities $“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”$ can be arranged on the timeline as :

Here, depth is $4$ because intervals $2,4,5$ and $6$ are conflicting i.e. activities $b,d,e$ and $f$.

Rooms can be assigned as :

Given graphical approach can be checked here also.

---

Very nice way of connecting different concepts... But timeline/stack methods seem suitable for this type of questions..

---

Won’t an array be more suitable? We just assign a,b etc to one of the array indices (room) when starting point is arrived and then remove them when ending point is arrived for them. The maximum size of array that is recorded during the whole procedure will be the answer.

---

This solution is given in corman.

---

NIce explaination

Answer 2

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

Answer 3

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

Answer 4

Total 4 rooms required. Option B is the answer.

Comments

best explaination