I am teaching a class that has n teaching assistants, each of whom hold office hours outside, at JavaCity

Subject:Computer SciencePrice: Bought3

Share With

I am teaching a class that has n teaching assistants, each of whom hold office hours outside, at JavaCity. The ith TA holds office hours starting at time Si and ending at time Ei . Each TA holds exactly one office hour (which may last any amount of time, not necessarily one hour, and different TAs may have different interval lengths, which may overlap with one another). Attendance has been low because students, being ICS majors, are afraid of the sun, so the department announces that all TAs who do not have a student visit them this week will be fired1 . Because all of our teaching assistants are awesome2 , we want to ensure that none get fired. However, due to student fears of the sun, we want to minimize the total number of visits made to TAs. For purposes of this problem, assume each TA's office hour time is one continuous interval with no breaks, and that a student visiting the sundeck at time t counts as visiting all TAs whose office hours interval contains t. Also assume that student visits are "instantaneous," in the sense that the amount of time a student stays in the sun is negligible - formally, each student visits the deck at a single point in time. This also helps to avoid exposing a student to the sun unnecessarily. You propose the following: first, we sort all of the intervals by end time. We send a student to attend office hours at the moment immediately prior to the end of the first ending interval. We remove from our input all TAs who overlap with this time, and if the remaining set is non-empty, we repeat. Prove that the greedy algorithm in the previous statement minimizes the number of students we need to send to visit TAs. For purposes of this homework this quarter, it is sufficient to demonstrate that for any optimal solution, there is an equally optimal choice of student visits that includes your first choice.