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?
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.
according to above concept ,how will we create a graph here and their connections ?plss help
Explanation: Room1 – As
Room2 – Bs
Room3 – As
now A ends (Ae) and now Room3 is free
now A ends (Ae) and Room1 is free
now B ends Room2 is free
now D ends Room3 is free
now E ends Room1 free
now F ends Room4 free
now G and H ends.
Totally used 4 rooms
We need "minimum" 4 room to accommodate all activities A to H as per conditions
Total 4 rooms required. Option B is the answer.
This type of problem can be solved by array representation of starting time ( taking +1) and ending time (taking -1 )
now taking sequence from array and sum them for getting largest positive no
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
Could you please provide some reference for this solution ?
Sir I have ordered GO PDF on 16 Aug 2018 still ...