Is there a name for the algorithm solutions for "booking rooms with the least room switches"?

Question

I was discussing with a co-worker a problem we were having with a piece of software we deploy, and he mentioned how it was similar to the conceptual problem of booking rooms over a course of time and the algorithm should output the room bookings that requires the least switches (so for example, an optimal solution may be staying in one room for 3 days, and the rest in another room, only requiring two switches).

Is there a name for such a problem in algorithms?

Answer 1

Originally I posted something regarding the minimum set cover problem. Although you can describe your problem as a minimum set cover problem, if we assume "room bookings" are over consecutive days, your problem can be more succinctly described with a different problem.

The interval cover problem¹ consists of one big interval (call it (a,b)), and a bunch of subintervals (call them (a_i, b_i)). Our goal is to cover the one big interval with as few subintervals as possible.

Finding the minimal coverage of an interval with subintervals is a question posted about 5 years ago which asks for an efficient solution, and the accepted answer shows that the greedy solution is optimal. Within the context of room bookings, the "greedy solution" would be basically to start from the beginning of the period and always pick the booking with the latest end date.

The idea of course with this problem is that the each "subinterval" is a booking, so the fewer subintervals we need, the fewer bookings, and hence the fewer "switches" we need.

---

^{1 I'm not actually 100% sure that this is the correct name, but if you were to say "interval cover problem", the listener would probably think of the same thing.}