Problem 1: A day at a crowded beach. You are back at the beach, but now it is too crowded. You have only k umbrellas. You run your optimal greedy algorithm from the previous homework, and you realize that the minimum number of umbrellas needed to cover everyone is larger than k. You decide to try to cover as many people as possible with the k umbrellas you have available. Formal description: You are given 21,...,In E Z, and some k,LEN. You want to find a collection of intervals 1.... CR, each of length L, such that the number of points in 21, ..., that fall inside IU... UI is maximized. Describe a polynomial-time algorithm for this problem. That is, the running time of your algorithm should be at most polynomial in n. Prove that your algorithm is correct and that it runs in polynomial time. For example, if the input is x1 = 1, 22 = 3, 23 = 4,24 = 6,25 = 9, 36 = 10, 27 = 11, 2g = 12, 29 = 15, 210 = 17, k = 3, and L=3, then an optimum solution is 1,4), (9, 12), 14, 17). an HHHHHHHHHHHHHH 1 ! 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 Hint: Use dynamic programming. Problem 1: A day at a crowded beach. You are back at the beach, but now it is too crowded. You have only k umbrellas. You run your optimal greedy algorithm from the previous homework, and you realize that the minimum number of umbrellas needed to cover everyone is larger than k. You decide to try to cover as many people as possible with the k umbrellas you have available. Formal description: You are given 21,...,In E Z, and some k,LEN. You want to find a collection of intervals 1.... CR, each of length L, such that the number of points in 21, ..., that fall inside IU... UI is maximized. Describe a polynomial-time algorithm for this problem. That is, the running time of your algorithm should be at most polynomial in n. Prove that your algorithm is correct and that it runs in polynomial time. For example, if the input is x1 = 1, 22 = 3, 23 = 4,24 = 6,25 = 9, 36 = 10, 27 = 11, 2g = 12, 29 = 15, 210 = 17, k = 3, and L=3, then an optimum solution is 1,4), (9, 12), 14, 17). an HHHHHHHHHHHHHH 1 ! 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 Hint: Use dynamic programming