0

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?

user248884
  • 123
  • Question - Do you already have a solution in your mind, as in, do you know how you would do it without the assistance of computers? If not, do the stakeholders know. What is the status quo? – Aphton Oct 13 '18 at 12:53
  • @Aphton I have explained my solution (Best Fit). This post was to garner responses from others who also might have thought about this problem. – user248884 Oct 13 '18 at 13:00
  • You would keep track of unused space, so there is very little overhead. – gnasher729 Oct 13 '18 at 15:21
  • @gnasher729 How would we do that? To find the most optimum space, we will always traverse through all the N slots. – user248884 Oct 13 '18 at 15:22
  • I have a question: Assume that you parked a car in slots 5-6, then a bus comes and you park it on slots 1-4. Then the car wants to leave, you remove the bus, then take the car out then put the bus back? – Mandrill Oct 14 '18 at 00:03
  • @Mandrill No, Its assume that there is a passway. Only the unparking vehicle will move. – user248884 Oct 14 '18 at 09:52

1 Answers1

1

You want to allocate vehicles as near to the entrance as possible. I assume that each vehicle counts, so instead of allocating 4/1/1/1/1, you would prefer 1/1/1/1/4 which moves four vehicles to the front, and moves one vehicle back.

I also assume that vehicles arrive, you assign them a slot, and eventually they leave. No vehicle is moved once parked.

First you gather some statistics - how many two-wheelers, cars and buses do usually arrive? Then you reserve slot 1-4k for two wheelers, 4k+1 to 4l for cars, 4l+1 to n for buses so that they usually fit.

Each vehicle goes into the first available slot in its area. If the area is filled, you move to the previous area(s). If they are filled, you move the vehicle to the next area. To simplify things, buses only move to slots 4j+1 to 4j+4 for some j, cars move to 2j+1 to 2j+2 for some j.

This makes sure that two wheelers tend to come first, then cars, which makes the cost minimal.

gnasher729
  • 44,814
  • 4
  • 64
  • 126
  • If I understand right, your solution is to basically have demarcated regions for the 3 types of vehicles and when the respective slots are full, we can try for the available slot in other sections? Its a good approach but how do you prove its an optimum one? Second, it violates the requirement that each vehicle should be allocated nearest to the gate. By your schema, the bus will always be parked towards the last section irrespective if there is available space before it or not. – user248884 Oct 14 '18 at 09:55
  • @user248884: gnasher729's answer addresses an important consideration in memory allocation: fragmentation of free space (or available memory addresses, when memory address space is in short supply e.g. in 32-bit processes). Fragmentation means that large allocation requests couldn't be made despite the availability of total free space because the remaining free space are fragmented (i.e. there are occupied spots scattered around, which break up the free space into smaller pieces). Whether the fragmentation problem is important for your project is ultimately your own decision. – rwong Oct 14 '18 at 09:59
  • @user248884 Before considering the issue of "optimality" (however you choose to define it), you might need to first decide what is the statistical model of vehicles *departing* their parking lot. Otherwise, a certain usage pattern can be constructed so that fragmentation will always happen. – rwong Oct 14 '18 at 10:06