As part of a new art-film awareness program, Cinemas inc. has $n$ special single-screen movie theaters where they will show $n$ art films over the next $d > n$ days (each film is shown at each theater for exactly one day). In a bit of bad timing the sound systems at each of the theaters need to be upgraded during this time, and all of the accompanying films need their audio tracks re-compressed so that they can play on an upgraded sound system. Cinemas inc has one audio technician for these $n$ theaters; on any given day the technician can go to any of the theaters, where they upgrade both the sound system and the film before the first showing of the day. Cinemas inc needs all of the sound systems and films upgraded by the end of the $d$ days, so the technician needs to figure out when to go to each of the $n$ theaters to perform the upgrades.
Any order would suffice if it weren't for the small issue of compatibility: a non-recompressed film can play on an upgraded sound system (it is backwards-compatible), but a re-compressed film cannot play on a non-upgraded sound system. The question is, if you are given as input the schedule of $n$ films (which theater has which of the $n$ films on each of the $d$ days), can you output which upgrades the technician should make on which day such that
(a) All films and sound systems are upgraded
(b) The upgrades do not interfere with any of the shows
Questions
- Consider the algorithm that puts the technician at one theater, say the first one, every single day. and just has them upgrade whatever comes through that theater. Give a small counter-example ($d \leq 5$) to show that this algorithm does not work.
- Consider the algorithm that puts the technician at theater $i$ on day $i \leq n$ (and has them upgrade the system and film at theater $i$.) Give a small counter-example ($d \leq 5$) to show that this algorithm does not work.
- Give an efficient algorithm(including a proof and running time analysis) that computes a solution to this problem.
- Run your algorithm on the example from (2) and show a reasonable amount of work.
My Attempt
I have found parts (1) and (2) to be pretty self-explanatory, however I am having trouble on part (3) (and therefore part (4)). I know that we must use the Gale-Shapley algorithm to produce stable matchings for films and theaters, however I am not exactly sure how to construct these preference lists and when I do have a stable matching, how to interpret these pairs as a solution to the problem.
Any help would be greatly appreciated. Thank you!