Yes, thank you.
That condition was initially because I didn't order the activities first.
Now I've changed it with that little memory of the last assigned activities
and it is NlogN.
On Tue, Apr 14, 2020 at 9:28 PM porker2008 wrote:
> Oh didn't notice that you override the equal() to for
Oh didn't notice that you override the equal() to for checking overlap.
As Matt pointed out, this is not efficient because you have to run through
the entire list to determine whether the new activity can be assigned to C
or J,
and it leads to O(N) to process each new activity and hence O(N^2)
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
I think the running time of your solution is O(N log N) unless you think
otherwise.
--
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
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
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
If I have the input:
99 150
1 100
100 301
2 5
150 250
What I showed in the final String is the assignment of this activities
in the entrance order. In that case, the result is:
JCCJJ
The first Activity is assigned to J, then next to C because intersects
in time with the first activity, the
Your solution simply does not work.
You need to process the activities based on their start time (or end time)
instead of the order given in the input.
--
You received this message because you are subscribed to the Google Groups
"Google Code Jam" group.
To unsubscribe from this group and stop
