edited by
14,103 views
50 votes
50 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$
edited by

11 Answers

6 votes
6 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.
4 votes
4 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.
3 votes
3 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

Answer:

Related questions

25 votes
25 votes
3 answers
4
Kathleen asked Sep 17, 2014
7,494 views
What is the weight of a minimum spanning tree of the following graph?$29$$31$$38$$41$