Problem 1: A day at the beach. In this problem we will implement the greedy algorithm that we designed for the homework assignment. A group of n people are lying on the beach. The beach is represented by the real line R and the location of the i-th person is some integer ti E Z. Your task is to prevent people from getting sunburned by covering them with umbrellas. Each umbrella corresponds to a closed interval I = [a, a + L) of length L N, and the i-th person is covered by that umbrella if x; E I. Design a greedy algorithm for covering all people with the minimum number of umbrellas. For example, if the input is x1 = 1, X2 = 3, x3 = 5, and L = 2, then an optimum solution is the set of two umbrellas placed at positions 2 and 5, covering intervals (1, 3) and (4,6]. 1 3 2 6 4 5 The input consists of a sequence of positive integers. The first number is L, followed by n, followed by n numbers X1,..., In. The output of your algorithm should be the leftmost endpoints of the umbrellas, sorted in increasing order. Submission and Implementation Details: Submit to Gradescope. Input/Output is through console (e.g. if using Python, simply using input and print functions). Print each sorted endpoint on a separate line. Please carefully follow these instructions because submissions will be automat- ically graded. All test cases will be valid. You don't need to implement checks for invalid inputs. Submit only one file written in a language of your choice. - Python3: Filename: beach.py - C/C++: Filename: beach.cpp Compilation: g++ beach.cpp -o beach.out - Java: Filename: beach.java Compilation: javac beach.java Example 1: Example 2: Input: 4 Input: 2 1 3 1 5 3 6 10 Output: 1 5 Output: 1 6 Problem 1: A day at the beach. In this problem we will implement the greedy algorithm that we designed for the homework assignment. A group of n people are lying on the beach. The beach is represented by the real line R and the location of the i-th person is some integer ti E Z. Your task is to prevent people from getting sunburned by covering them with umbrellas. Each umbrella corresponds to a closed interval I = [a, a + L) of length L N, and the i-th person is covered by that umbrella if x; E I. Design a greedy algorithm for covering all people with the minimum number of umbrellas. For example, if the input is x1 = 1, X2 = 3, x3 = 5, and L = 2, then an optimum solution is the set of two umbrellas placed at positions 2 and 5, covering intervals (1, 3) and (4,6]. 1 3 2 6 4 5 The input consists of a sequence of positive integers. The first number is L, followed by n, followed by n numbers X1,..., In. The output of your algorithm should be the leftmost endpoints of the umbrellas, sorted in increasing order. Submission and Implementation Details: Submit to Gradescope. Input/Output is through console (e.g. if using Python, simply using input and print functions). Print each sorted endpoint on a separate line. Please carefully follow these instructions because submissions will be automat- ically graded. All test cases will be valid. You don't need to implement checks for invalid inputs. Submit only one file written in a language of your choice. - Python3: Filename: beach.py - C/C++: Filename: beach.cpp Compilation: g++ beach.cpp -o beach.out - Java: Filename: beach.java Compilation: javac beach.java Example 1: Example 2: Input: 4 Input: 2 1 3 1 5 3 6 10 Output: 1 5 Output: 1 6