The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+23 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?

- $3$
- $4$
- $5$
- $6$

+29 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.

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

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.

And yes, you can do like that- graph making is just another way.

+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

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.

+5

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.

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.

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

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.

+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

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

“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}”

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

+11 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

+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

0 votes

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.

Applying the logic on the given order give answer as B ie 4.

–1 vote

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

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

- All categories
- General Aptitude 1.4k
- Engineering Mathematics 5.9k
- Digital Logic 2.3k
- Programming & DS 4.2k
- Algorithms 3.6k
- Theory of Computation 4.6k
- Compiler Design 1.7k
- Databases 3.3k
- CO & Architecture 2.9k
- Computer Networks 3.3k
- Non GATE 1.2k
- Others 1.3k
- Admissions 506
- Exam Queries 480
- Tier 1 Placement Questions 22
- Job Queries 64
- Projects 15

40,748 questions

47,470 answers

145,581 comments

62,234 users