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

Here we need minimum 4 rooms at a given time as Maximum running count = minimum rooms.

 

---

Just apply the logic

---

Ans 4

Answer 1

 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

Comments

@Gate Ranker18,

Could you please provide some reference for this solution ?

Answer 2

ans== 4 as we every new room is allocated when rest all allocated previously are filled

Answer 3

We can solve this by using Gantt chart also.

Option (B) is right answer.

Answer 4

Now find chromatic number

Answer 5

this is a best and easiest apporoch for solving this quation

Answer 6

This problem can be solved using a simple timeline (parenthesis) approach. We plot the start and end time of each activity on a single time axis, where the start of an activity represents its entry into a room and the end represents leaving the room. An activity occupies a room for its entire duration, so if multiple activities overlap at the same time, they must be assigned to different rooms.

By observing the diagram, we count how many activity lines overlap at any instant. The maximum overlap occurs when activities b, d, e, and f are running simultaneously, giving an overlap count of 4. Hence, the minimum number of rooms required to schedule all activities without conflict is 4.

Final Answer

Minimum number of rooms required = 4