(45 pts.) Scheduled Maintenance Suppose you are in charge of maintenance for a college campus. You manage n pieces of equipment which need to be regularly inspected, some more often than others. The equipment is evenly distributed across 20 different buildings. Every day, you choose a building to visit, and then spend the day inspecting k pieces of equipment there. Here is one way you could decide your schedule using priority queues: You maintain a priority queue A containing each piece of equipment, with the key being the next day when the equipment should be inspected as an integer, counting days from some arbitrary starting point). The highest-priority piece of equipment is then the one which needs to be inspected soonest, and you pick its building to visit. You also keep a separate priority queue B; for each building, including only the equipment inside that building (with the keys as above). Once you've decided which building to visit, you inspect the top k items from the corresponding priority queue. After each day, you need to update the queues to be ready for the next day, taking into account that the k pieces of equipment you just inspected now don't need to be inspected again until some later dates. Let's look at how long the whole process could take, as a function of n. (a) Describe how you would use the priority queue operations to implement the schedule above, including updating the queues for the next day. In total, how many operations of each type would you apply to A and to Bi (assuming you choose building i)? (b) Suppose you can't inspect very many pieces of equipment each day, so that k = 0(1). What choices of priority queue implementations should you use for A and B; to get the best asymptotic runtime for your procedure in part (a)? State the asymptotic runtimes you get for your operations on A and B; separately. (C) Suppose instead you're feeling very energetic and can inspect k = (n) pieces of equipment each day. Does your choice of implementations from part (b) change? Either way, state the new asymptotic runtimes for your operations on A and B; separately. (45 pts.) Scheduled Maintenance Suppose you are in charge of maintenance for a college campus. You manage n pieces of equipment which need to be regularly inspected, some more often than others. The equipment is evenly distributed across 20 different buildings. Every day, you choose a building to visit, and then spend the day inspecting k pieces of equipment there. Here is one way you could decide your schedule using priority queues: You maintain a priority queue A containing each piece of equipment, with the key being the next day when the equipment should be inspected as an integer, counting days from some arbitrary starting point). The highest-priority piece of equipment is then the one which needs to be inspected soonest, and you pick its building to visit. You also keep a separate priority queue B; for each building, including only the equipment inside that building (with the keys as above). Once you've decided which building to visit, you inspect the top k items from the corresponding priority queue. After each day, you need to update the queues to be ready for the next day, taking into account that the k pieces of equipment you just inspected now don't need to be inspected again until some later dates. Let's look at how long the whole process could take, as a function of n. (a) Describe how you would use the priority queue operations to implement the schedule above, including updating the queues for the next day. In total, how many operations of each type would you apply to A and to Bi (assuming you choose building i)? (b) Suppose you can't inspect very many pieces of equipment each day, so that k = 0(1). What choices of priority queue implementations should you use for A and B; to get the best asymptotic runtime for your procedure in part (a)? State the asymptotic runtimes you get for your operations on A and B; separately. (C) Suppose instead you're feeling very energetic and can inspect k = (n) pieces of equipment each day. Does your choice of implementations from part (b) change? Either way, state the new asymptotic runtimes for your operations on A and B; separately