I have a problem that is similar to the interval scheduling algorithm but it involves priorities. My data sets consist of the following data:

- **Cars** with the start and end time of parking, along with their one or more attributes (e.g. electric vehicle, motorcycle, handicapped).
- **Parking spots** along with zero or more attributes and lot number.
- **Attributes** with their priorities. For example if the property `handicapped` is given a value of 1, cars that have that attribute should be assigned a parking spot first.

There is no overnight parking so I have divided the data into buckets of days. Start and end times are in increments of 5 minutes (not sure if this is important).

### Objectives

This problem comes from overhauling an existing algorithm, which after observing how users interact with the system, it could definitely use improvement.

My first step is to get something going that can **produce one or more possible solutions that meet all of the provided attributes**. For example, a limo cannot be assigned to a motorcycle spot. There may not be a complete solution given the inputs, if there are 5 electric vehicles but only 4 spots, the algorithm should still try to assign 4 of them (the 4 that have the highest priority).

Given multiple solutions, the "best" solution would minimize the number of open lots at any given time (ideally all the cars parked in the same lot). Even if it is a small block of time in the middle of the day, the lot can still be closed to minimize the cost of security guards.

## What I have tried

1. Find all the valid parking spots for each car.
1. Sort each parking spot list in ascending order of the sum of priorities for the parking spot.
1. Sort the list of cars in descending order of sum of priorities.
1. Attempt to assign each car in order of the sorted parking spots. If the spot is taken for that time then try the next one and so on.

I am hoping to make this more efficient by taking into account the interval for each car, as it currently isn't being taken into account when sorting.

I stumbled upon Google Optimization Tools and it looks similar to the [nurse scheduling problem](https://developers.google.com/optimization/scheduling/employee_scheduling) but with more constraints. A key difference is that each shift in the NSP is defined whereas the intervals in my problem can partially overlap.

## Questions

1. How can I model the problem?
1. Are tools like [Google OR-Tools](https://developers.google.com/optimization/) or [pyschedule](https://github.com/timnon/pyschedule) appropriate for solving this?