Question 1 (Activity Profit Maximization, Dynamic Programming) You are in charge of scheduling activities in a public meeting space. You have a set of requests for activities {01, ... , Qn} each activity a; has a start and end times of si and e, such that the activity occupies the time range [si, el. Also, each activity has a profit Pi that is independent of its duration. Your job is to select a subset of non-overlapping activities such that you marimize the total profit. You cannot schedule two activities that overlap in time as they are considered incompatible. The table below shows an example of six activities. The answer is illustrated in the following figure. 2 1 2 9 4 5 6 0 6 4 10 11 9 ei 5 10 6 12 15 19 Pi 5 6 10 2 7 8 4,2 92,6 aylo it 5 10 Develop a dynamic programming algorithm that selects a subset of compatible (non-overlapping) activities with a maximum profit. (Hint: Try to sort activities by end time and then develop a recurrence relation on the sorted list. The recurrence relation will indicate the maximum profit obtainable up-to an activity in the sort order.)