@Ashish
E(S1) = 0 // S1 is the time we start the first event , so no meetings could
be scheduled by then
E(F1) = 1 // the events are sorted by finish time, so no event could finish
before F1(first event)
Fill the Values E(S1+1) to E(F1-1) to E(S1) which should be 0.
Now if S2 precedes F1. E(S2) will have the value of E(S1) ( which is zero)
if S2 falls after F1, E(S2) will have the value of E(F1) ( which is 1).
E(F2) = Max ( E(s2) + 1 which occurs if S2 Falls after F1 -> the 2
meetings dont overlap
or E(F1)
For overlapping events E(F1) = E(S2)+1 = 1.
For Non Overlapping Events E(S2) + 1 = 2.
you can try simple examples.
On Wed, Mar 2, 2011 at 9:19 PM, Ashish Goel <[email protected]> wrote:
> How is E(s2) is calculated? Why E(S2)+1
>
> Best Regards
> Ashish Goel
> "Think positive and find fuel in failure"
> +919985813081
> +919966006652
>
>
> On Wed, Feb 9, 2011 at 5:05 PM, Ujjwal Raj <[email protected]> wrote:
>
>> Input: n meetings
>> A meeting e(i) has start time s(i) and finish time f(i).
>> Sort n events based on there finish time f(i)
>> Say sorted meeting(based on finishing time) are:
>> e1,e2,e3,e4,...en
>>
>> E(t): denotes the maximum no of meetings conducted where 0 <= time <= t.
>>
>> E(f1) = e1
>> E(f2) = max(E(s2) + 1), E(f1));
>> E(f3) = max(E(s3)+1), E(f2));
>>
>> Make array of E based on finishing times.
>> So your array will have values of E at different finishing times
>> f1 E1
>> f2, E2
>> f3 E3
>> f4 E4
>>
>> so E2 means maximum no of events between time >= f2 and < f3.
>>
>> Hope it is now clear.
>>
>>
>> On Wed, Feb 9, 2011 at 12:59 PM, Sachin Agarwal <
>> [email protected]> wrote:
>>
>>> didn't quite get it, can you please elaborate.
>>> thanks
>>>
>>> On Feb 8, 10:38 pm, Ujjwal Raj <[email protected]> wrote:
>>> > Use dynamic programming:
>>> > 1) Sort the events in order of finishing time.
>>> > f1, f2, f3, f4, ... fn
>>> >
>>> > E(fn) = E(sn) + 1;
>>> > Solve the above recursion
>>> > sn is start time of event n
>>> >
>>> > On Wed, Feb 9, 2011 at 11:30 AM, Sachin Agarwal
>>> > <[email protected]>wrote:
>>> >
>>> >
>>> >
>>> >
>>> >
>>> >
>>> >
>>> > > Suppose I have a room and I want to schedule meetings in it. You're
>>> > > given a list of meeting start and end times. Find a way to schedule
>>> > > the maximum number of meetings in the room.
>>> >
>>> > > --
>>> > > You received this message because you are subscribed to the Google
>>> Groups
>>> > > "Algorithm Geeks" group.
>>> > > To post to this group, send email to [email protected].
>>> > > To unsubscribe from this group, send email to
>>> > > [email protected].
>>> > > For more options, visit this group at
>>> > >http://groups.google.com/group/algogeeks?hl=en.
>>>
>>> --
>>> You received this message because you are subscribed to the Google
>>> Groups "Algorithm Geeks" group.
>>> To post to this group, send email to [email protected].
>>> To unsubscribe from this group, send email to
>>> [email protected].
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>>
>> --
>> You received this message because you are subscribed to the Google
>> Groups "Algorithm Geeks" group.
>> To post to this group, send email to [email protected].
>> To unsubscribe from this group, send email to
>> [email protected].
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
