Marking Scheme (for both questions): Program is correct and must use greedy (8 points) Program is correct but does not use greedy 4 points Program is correct, uses greedy, but fails on few testing cases 4 points Program is correct, uses greedy, but fails on many testing cases 2 points Program does not run, or fails on most testing cases 1 point Program has the required efficiency (8 points) Program only fails on few test cases but meets the efficiency 6 points Program is correct but slightly inefficient 3 points Program is correct but significantly inefficient 1 point Pseudocode is in plain English and is a clear description of your algorithm (3 points) Using only slightly modified Python program for pseudocode 1 point Parameters, return, and function name are as specified (2 points) Program style and logic are clear and concise (2 points) Explanation on the complexity of the algorithm is clear (1 point) Comments are appropriate and program is easy to understand (1 point) Note: Calling Python functions/methods on a list costs a certain complexity. For instance, len() takes constant time, sort( takes O(n log n) time, max( ), min( ), or sum() takes O(n) time. T3_1 (25 Marks) Platform Scheduling: On a day, Kingston VIA station has a set of n trains arriving and departing. Each train has a known arrival time and a known departure time. Each train needs to be assigned a platform for arrival. A train can only arrive at a platform when its previous train has already departed. That is, a train with an arrival time 9:00 can't use a platform where its current train departs at 9:00 or later than 9:00. Kingston VIA station has k platforms (we treat k as a constant) and we assume there are always enough platforms to accommodate all n trains. Provide an algorithm with O(n log n) complexity to accommodate n trains using a minimum number of platforms. Write a function platform_assignment(trains) that take a list of tuples as input and returns a list of platform indices. Input [(930, 1020), (1000, 1340)] represents two trains that the first arrives at 9:30 and departs at 10:20, and the second arrives at 10:00 and departs at 13:40. Your function should return [0, 1] meaning the first train is assigned to platform 0 and the second train is assigned to platform 1. The order of the platforms does not matter. More examples, platform_assignment([(1220, 1300),(930, 1000))) returns [0, 0] platform_assignment([(830, 920), (700, 840), (930, 1100)]) returns [0, 1, 1] or [1, 0, 0]