There is one meeting room in a firm. There are N meetings in the form of (S[i], F[i]) where S[i] is the start time of meeting i and F[i] is finish time of meeting i. The task is to find the maximum number of meetings that can be accommodated in the meeting room. Print all meeting numbers
Examples:
Input : s[] = {1, 3, 0, 5, 8, 5}, f[] = {2, 4, 6, 7, 9, 9}
Output : 1 2 4 5
First meeting [1, 2]
Second meeting [3, 4]
Fourth meeting [5, 7]
Fivth meeting [8, 9]
This is a typical greedy problem and the solution is to sort on ending time and select ones that don’t conflict with the meetings that we chose. There are two other greedy strategies and it’s easy to prove that they don’t work shown below.
Moreover, it’s easy to prove by contradiction that sorting on end time and greedily select meetings works.
s = [1, 3, 0, 5, 8, 5]
f = [2, 4, 6, 7, 9, 9]
ret,last = [],-1
for i,(s,e) in sorted(enumerate(zip(s,f)),key=lambda x:x[1][1]):
if s >= last:
ret.append(i+1)
last = e
return ret