Quote:
Originally Posted by Mark Sir Link
The length of the array is increased to units + 1 to reconcile the idea of each element of the array scaling from the beginning of that index that index to the beginning of the next, IE, 0-1, 1-2, ..., 100-0
snip
|
As best as I can tell, this is just an expensive way to compute (min+max)/2, which isn't right.
My hint would be to first consider the lot when it is empty; the first car comes along and parks anywhere at all. After this event, we have 1 car in the lot and the lot is now linear (the endpoints being the front and end of our first car). On top of that, the size of the lot has shrunken to
N-2. Then you just have to consider every possible arrangement of cars in a linear lot of length
N-2.
What do you have after the next car arrives?