That being said, I have problem that I'll elucidate and I know that Convex Hull algorithm will best fit the need. I coded my rendition of the Jarvis' algorithm.
Problem statement (updated): Suppose there are n events and each event is represented by a 3-tuple (x, y, z) where x is the start time, y is the end time and z is the cost of the event. for example:
x y z 1 1 3 1 4 6 1 2 10 2 4 9 2 6 10 2 5 20 4 2 8 4 8 20 4 1 3
Suppose that this represents all those possible events that I can attempt to earn money but clearly, I cannot attempt them all because for some events, start time overlaps with some other events, creating a deadlock. The best solution is I schedule the events in such a way that I "handpick" certain event that do not clash while not decreasing my profit (not necessarily maximize but I should not also face a loss). For example:
x y z 1 2 10 2 4 9 4 8 20
Why I think Convex Hull best fits the solution?
Well, what I did was, instead of using the 3-tuple, I calculate how much time each event will actually take (by subtracting x from y) so this way I get a set of pair of points on a Cartesian plane. Now, applying the Jarvis algorithm, I'll get one convex quadrilateral that covers all the points exactly once and returns to the original point (The Traveling Salesman Problem). This way, I'll get all those points I can schedule without getting deadlocked and my profits will be maximized.
I implemented the Jarvis algorithm from the wiki link above.
#!/usr/bin/perl use strict; use warnings; my @AoA; # an array of arrays to represent the points. while(<DATA>) { push @AoA, [ split ]; } my @sorted = sort { $a->[1] <=> $b->[1] } @AoA; # thanks moritz! =head for my $aref ( @sorted ) { print "\t [ @$aref ],\n"; } =cut # implementing the Gift Wrap algorithm. # the @sorted array contains all the points and that too in the sorted + order # the sorting helps identify the "left most point". my (@P, @endPoint, @pointOnHull, $i, $flag1, $flag2); @pointOnHull = @{$sorted[0]}; # the "left most point" $i = 0; do { $P[$i] = [ @pointOnHull ]; @endPoint = @{$sorted[0]}; for my $j (1 .. $#sorted) { # determine position of j'th element relative to line P[i] to +P[endPoint] # it should lie to the right of the line P[i] to P[endPoint] # we check that if the current point's x and y co-ordinates # are greater than, in every respect, the current end point. if(${$sorted[$j]}[0] > $endPoint[0] && ${$sorted[$j]}[1] >= $e +ndPoint[1]) { $flag1 = 1; } # check if the current end point is not a point on the hull. if($endPoint[0] != $pointOnHull[0] && $endPoint[1] != $pointOn +Hull[1]){ $flag2 = 1; } if($flag1 || $flag2) { @endPoint = @{$sorted[$j]}; } } $i++; @pointOnHull = @endPoint; } until ($endPoint[0] == ${$P[0]}[0] && $endPoint[1] == ${$P[0]}[1]); # Array P is the convex hull for my $aref ( @P ) { print "\t [ @$aref ],\n"; } __DATA__ 20 50 50 10 43 45 23 46 48 93 324 45 245 437 2315 4576 135 457
the code is going into an infinite loop and I'm finding it difficult to grasp why is it doing so? Any pointers? I'm unwilling to use any external module(s).
Even if convex hull algorithm does not qualify as the best solution, I'd ask respected monks to comment on the code at least. :)
PS: The problem statement may sound familiar to some. It was a problem in the ACM-ICPC 2011 final round. I'm not recalling the exact words of the problem. I was in the pre-final year of college and this was the only problem my team couldn't crack and we lost to this other team. It has been bugging me since then!UPDATE:The exact problem statement can be found here. Thanks to hdb. problem F.
In reply to Convex Hull Problem by code-ninja
| For: | Use: | ||
| & | & | ||
| < | < | ||
| > | > | ||
| [ | [ | ||
| ] | ] |