This question is an extension to this question. I am also brainstorming on this problem statement wherein a 1-dimensional parking lot having N slots will be having varying size parkings to do. A two-wheeler occupies 1 slot, a car occupies 2 slots and a bus occupies 4 slots.
We have to design a system that efficiently allocates space for these. The efficiency metric is that we should be able to accommodate maximum vehicles and allocate them as near to the entrance (assuming slot 1 is the closest then 2, then 3 and so on .. )
Unlike in the referred post, I seek advice on what algorithm we can use to make the allocation. We can draw a parallel between this problem to the memory allocation that happens in OS. This could be considered such as there are many processes of varying size (1, 2 and 4) which need to be allocated space in the main memory (our parking lot) Incase of variable sized memory allocation, there are 3 algorithms:
1. Best fit: allocate the most optimum space 2. Worst Fit: allocate the least optimum space 3. First Fit: allocate the first available space
Best Fit may be a good option to consider but it has a higher overhead of time. First Fit is a good option to consider but it may cause wastage of space.
Is there any other algorithm/ data structure that could be used for an allocation such as this?