When we sort the activities on start time, we get something similar to the
following: (1,2),(1,3),(2,4),...,(s,e), or whatever fits your sample set so
long as the activities that start the earliest are toward the front. From
there (and I'm skipping a set or two, so bear with me), the algorithm
assigns activities in the following way:
C: (1,2)
J: (1,3)
Remaining activities: (2,4),...,(s,e)
>From here, we know two things:
1) No activity is going to start before 1 because we sorted the activities
from earliest start to latest start
2) C is available at or after 2, and J is available at or after 3
Moving forward, the question that we must ask ourselves is, "Does the next
activity start before C becomes available?" This means that we do not care
about which activities C and J have been assigned. All we care about is
when their last activity ends.
With respect to order notation:
Sort: O(nlogn)
Assignment: O(n)
Reorder: O(nlogn)
Total: O(nlogn) + O(n) + O(nlogn) => O(2nlogn) + O(n) => O(nlogn)
In regards to your code, when you run this line:
{if (!listActividadesC.contains(nextAct) || listActividadesC.isEmpty())}
the code starts at the beginning of the list and walks aaaalllll the way to
the end just to check the end time. This results in O(n) time for each
activity. For n activities, the runtime becomes n * O(n) => O(n * n) =>
O(n^2).
In conclusion, we can't do anything about the sorting time or the
reordering time. However, we can shorten the assignment time by tracking
the latest end time of each partner to avoid traversing all of their
activities for each assignment. I hope this helps.
Best,
Matt
On Tuesday, April 14, 2020 at 11:56:18 AM UTC-4, Nuria Ruiz wrote:
>
> Thank you poker2008,
>
> I see now, too bad :(.
>
> I've ordered first the tasks and now the code passes test set.
>
> But I don't know how to optimize the solution for Big-O N-LOGN.
>
> In the Analysis they say:
> The running time of this solution is O(*N*2), which is fast enough to
> solve this test set. To optimize the solution to O(*N* log *N*) time, we
> can efficiently check whether an activity can be assigned to Jamie or
> Cameron by keeping track of the end time of the last activity assigned to
> each partner and comparing this to the start time of the new activity. In
> this case, only O(*N*) extra time is needed after sorting the activities
> by their start time.
>
> I think that running time is not possible, Do you have some
> example with NlogN?
>
> Here my solution <http://ParentingPartneringReturns/Solution.java>
>
> Nuria
>
>
> On Mon, Apr 13, 2020 at 10:02 PM porker2008 <[email protected]
> <javascript:>> wrote:
>
>> Your printing order is correct.
>> My point is for some specific input, there is a solution but your program
>> will output *IMPOSSIBLE*
>>
>> e.g.
>>
>> Input:
>> *1*
>> *4*
>> *0 1*
>> *5 6*
>> *0 2*
>> *1 6*
>>
>> Expected output:
>> *Case #1: CJJC* (or *JCCJ*)
>>
>> But your program will return *IMPOSSIBLE*
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Google Code Jam" group.
>> To unsubscribe from this group and stop receiving emails from it, send an
>> email to [email protected] <javascript:>.
>> To view this discussion on the web visit
>> https://groups.google.com/d/msgid/google-code/e34b0bcf-cd2f-4c89-908a-0a9e53c84d2a%40googlegroups.com
>>
>> <https://groups.google.com/d/msgid/google-code/e34b0bcf-cd2f-4c89-908a-0a9e53c84d2a%40googlegroups.com?utm_medium=email&utm_source=footer>
>> .
>>
>
>
> --
>
>
>
> *Nuria Ruiz Sánchez*
>
> Desarrollos y Aplicaciones
> (+34) 686 871 682
>
> [email protected] <javascript:>
>
> Palma de Mallorca
>
--
You received this message because you are subscribed to the Google Groups
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/google-code/f2d54cb0-5670-4071-a63e-7caee6c50224%40googlegroups.com.
