(95 pts.) Interference Suppose we have n cell phone towers, with various positions and signal strengths. For simplicity, we'll assume the towers are on the real line, so that for each tower i there is some interval [li, ri] CR where its signal can be received. Two towers interfere with each other if their intervals overlap; we want to find all towers which are subject to interference. (a) (5 pts.) A simple algorithm to find the interfering towers would be to check each tower in turn, computing its overlap with all other towers. What would be the asymptotic runtime of this algorithm? CSE 102, Winter 2021, HW 2 1 (b) (40 pts.) Describe an asymptotically-faster divide-and-conquer algorithm to find all interfering towers. Summarize the high-level idea of your algorithm in a few sentences, as well as giving pseudocode. (Hint: split up the towers based on li.) (c) (10 pts.) Give a recurrence for the runtime of your algorithm, and solve it asymptotically. (d) (40 pts.) Prove your algorithm correct