Design a greedy algorithm to solve the activity selection problem. Suppose there are a set of activities: a1, a2, ... an that wish to use a lecture hall. Each activity ai has a start time siand a finish time fi. A lecture hall can be used by only one activity at a time. Two activities can be scheduled in the same lecture hall if they are non-conflicting (fi<= sj or fj<= si) Your algorithm should find out the minimum number of lecture halls needed to hold all the activities. Write a program to implement your algorithm. For example: if the activities you need to schedule have the following start times and finish times,
4 7
6 9
7 8
1 3
1 4
2 5
3 7
then the output of your program is "the minimum number of lecture halls required is 3". Also indicate which activity will be scheduled in which lecture hall.