Register

GATE CSE 2003 | Question: 69

• edited by
24,946 views
72 72 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$

13 Answers

Best answer
77 77 votes

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 by
19 19 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

12 12 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.
9 9 votes
This question is similar to the question where arrival and departure time of trains are given and we have to calculate minimum no of platforms required. The logic is whenever job start/train comes cont++ when depart/end counnt-- then the maxm value of count in bw will be the ans.Note at the end count=0

eg .      as, bs be,cs,ce,ae

count: 1.   2 .   1 . 2.  1 .0

maxm value of count is 2 so two platforms/room req.
Page:
Voting & Accepting an answer helps improve the community
Answer:
← Previous · GATE CSE 2003 | Ques...Next → · GATE CSE 2003 | Ques...
← Previous in category · GATE CSE 2003 | Ques...Next in category → · GATE CSE 2003 | Ques...
Position:
Show:

Related questions

61 61 votes
5 answers 5 answers
14.7k
14.7k views
Kathleen asked Sep 17, 2014
14,684 views
GATE CSE 2003 | Question: 60, ISRO2007-45
A program consists of two modules executed sequentially. Let $f_1(t)$ and $f_2(t)$ respectively denote the probability density functions of time taken to execute the two ...
94 94 votes
11 answers 11 answers
31.5k
31.5k views
go_editor asked Apr 24, 2016
31,489 views
GATE CSE 2003 | Question: 62
In a permutation $a_1\ldots a_n$, of $n$ distinct integers, an inversion is a pair $(a_i, a_j)$ such that $i < j$ and $a_i a_j.$What would be the worst case time complex...
70 70 votes
9 answers 9 answers
20.2k
20.2k views
Kathleen asked Sep 17, 2014
20,161 views
GATE CSE 2003 | Question: 88
In the following $C$ program fragment, $j$, $k$, $n$ and TwoLog_n are integer variables, and $A$ is an array of integers. The variable $n$ is initialized to an integer $\...
75 75 votes
5 answers 5 answers
28.8k
28.8k views
Kathleen asked Sep 17, 2014
28,802 views
GATE CSE 2003 | Question: 70
Let $G= (V,E)$ be a directed graph with $n$ vertices. A path from $v_i$ to $v_j$ in $G$ is a sequence of vertices ($v_{i},v_{i+1}, \dots , v_j$) such that $(v_k, v_{k+1})...