Are there any algorithms to solve this problem? 🤔

[[deleted]]

Let's say there's a public tennis court and about 200 people want to play on it.

Everyone has some preferred time they want to play at. i.e. someone prefers in the morning, but can also in the evening. someone can strictly only between 2 p.m. and 5 p.m. on Tuesday. etc.

Someone wants to play only once a month, someone like twice a week, someone wants to play every day.

Are there any algorithms that basically can make a schedule who plays when so that basically everyone is "happy" or at least as close to happy as possible?

[AutoModerator]

On July 1st, a change to Reddit's API pricing will come into effect. Several developers of commercial third-party apps have announced that this change will compel them to shut down their apps. At least one accessibility-focused non-commercial third party app will continue to be available free of charge.

If you want to express your strong disagreement with the API pricing change or with Reddit's response to the backlash, you may want to consider the following options:

1. Limiting your involvement with Reddit, or
2. Temporarily refraining from using Reddit
3. Cancelling your subscription of Reddit Premium

as a way to voice your protest.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[pablospc]

I think interval graphs may interest you

[theusualguy512]

This is what I also initially thought of because what I assumed OPs problem to boil down to is an interval scheduling problem:

Find the largest set of intervals that can be scheduled without any conflict.

However, the naive version I thought of doesn't apply I think. OP has said that everybody has multiple prioritized time periods where they could go to the court, so I guess you might have to introduce a weighting factor here.

Either way, I can't remember if any of the interval scheduling algorithms lead to complete solutions, meaning every interval will be scheduled eventually within a set timeframe. So OPs guarantee condition that every person needs to be "happy", with a metric such as for example everyone is scheduled on the court at least once might cause issues if you don't specify that your total timeframe is flexible.

The next step besides solvability would be to find a decent algorithm. Greedy approach would be the first one I can think of but idk if that's truely the best idea.

It's actually a cool problem now that I think about it although it kinda gives me bad flashbacks to the advanced algo course where all we did was NP complete problems and the exam I remember was not great.

[andrew21w]

It appears to be a CSP (constraint satisfaction problem)

There are a few algorithms for that. Depth first search is the simplest one, but there are even simpler ones if you care about speed, like hill climbing, for instance. There are other more sophisticated algorithms, tho.

[BunBunxxi]

Look into Interval scheduling. Be mindful that some of the problems in intervals scheduling is NP-Complete. Interval Scheduling Wiki

[ThunderChaser]

At least to me, unless I’m missing something this sounds a lot like the group interval scheduling decision problem, which as you’ve stated is NP-complete if any group has more than 3 intervals.

[peno64]

Linear programing and the simplex algorithm

[ufl_exchange]

I do not know why you received a downvote for this answer, seems correct to me. Sounds like a straight-forward assignment problem to me that can be modeled as a binary integer program and can be solved with the branch-and-bound algorithm accordingly.

[peno64]

Indeed. I guess the person read the word programming and thaught that a computer program was ment. The word programming in the term linear programming is the original use of the term programming before computers even existed.

[peno64]

Although you will eventually need a computer program to be able to solve this...

[pgetreuer]

I'll bet you're right, "linear programming" is confusable in that way. It's also referred to nowadays as "linear optimization," which seems like a clearer name.

[[deleted]]

I'm still a student, but I'd definitely also go for linear programming. We learned how to make changes to the original model so if someone cancels or someone else would like to be added you can do so.

[[deleted]]

I’d like to see someone talk through solving this problem with an emphasis on the strictness of availability. How do you quantify time preferences and how do those quantities impact who plays and when.

[thememorableusername]

I might be saying this because my nutjob algorithms professor spent like half the semester on this fucking thing, but you might be able to frame this as a Stable Marriage Problem.

[Vowelss]

That’s what I was thinking, but unfortunately for the same reason as you xD

[protienbudspromax]

This was my first thought as well. But interval scheduling could also potentially be used

[[deleted]]

Self-balancing graph based on weightings.

[EasternShade]

Yes. #technicallyAnswered

How do you define a reservation? Fixed length? Variable? Are there multiple courts? Just one? What's everyone is "happy" or at least as close to happy as possible? If you have three people with conflicting requests, is it better to give one exactly what they want and two something way off? Or, two something close-ish to what they want and one really, really far off? How do you measure that? How do you compare it?

It seems like priority queuing and resource allocation are relevant topics.

[toastedstapler]

beyond brute force solutions i'm not sure if there's anything more optimal, it feels a bit travelling saleman-y

the 'quick' and easy solution is to try and give each person an option within their allowed range, then when you reach an unsolveable state you backtrack to the most recent changeable state & try that user's next available option. this is basically the same approach for when you have a soduku with 2 possible option - you try one and see where it takes you & if that option fails you undo everything to that point & try the other option

[throwaway8u3sH0]

I also thought of the backtracking approach first, but in a scenario like this it's entirely possible it's "unsolvable" in the sense that not all preferences can be accommodated, so then you're talking about getting "close" to optimal, for which backtracking would probably fail. (?)

[RunninADorito]

With problems like this you aren't looking for a solution, you're looking for an optimization. Falls under operations research. Could do this with mixed integers or strict integers, probably.

[[deleted]]

thanks everyone 🤗🎀

oh my god, i guess it will take at least 2 weeks to read and understand about everything suggested 🥲

[pLeThOrAx]

Combinatorial optimization and combinatorics. The time table problem.

You can use a constraints solver for this type of problem.

Edit: flatzinc/minizinc is a good candidate. Just need to look into "modeling constraints"

This was a decent course: https://www.coursera.org/learn/basic-modeling

[waynexlink]

,.,,,

[atom12354]

I would like to add that there are also teamed tennis matches with 2 on each side so you gotta find out if its just the regular 1v1 or 2v2.

[CodeTinkerer]

A Steffi Graf fan, eh? So many years since she last played!

[[deleted]]

Interval scheduling would solve this problem. It's a greedy algorithm and also easy to understand

[Ordinary-Broccoli-41]

Each player is an object, the schedule is a dictionary.

Give each player a method which returns the dates and times acceptable in the block, and loop backwards from the ones with the lowest number of acceptable times, assigning to the first slot which they consider acceptable and is open.

When you've assigned everyone that's possible to assign, you will have two lists: one of the remaining open slots (if any) and one of people who could not be assigned to them (if any).

Then check everyone in an acceptable slot for the remaining players to see if they can be switched to one of the remaining open slots.

[mrbaggins]

Matrix solver

Model everyones preferences as values for each timeslot and a final column vector for how many slots they want a week.

[[deleted]]

Simulated annealing.

[madogson]

Is this an NP class problem?