Greedy algorithm

A research laboratory has an expensive scanning probe microscope, shared between different work groups. Every day, groups interested in using the microscope on the next day sive communicate their requests, indicating the time intervals for which they want to book the resource. The head of the laboratory must select a set of compatible requests from each other, and wants to do it in order to satisfy the maximum number of requests. Two requests are among them compatible if the respective time intervals do not overlap. More formally, let us suppose that there are n requests, identified by the numbers 1, · · ·, n. Every request and a couple (si , fi ), where si indicates the instant of beginning and fi the instant of the end of the request the. Obviously, suppose si <fi . We will say that the requests i and j are compatible if fi ≤ sj o fj ≤ si . A subset of requests is compatible if its elements are two-by-two compatible. We ask you to write a program that, given a set of requests, calculates a subset compatible with maximum cardinality. Each request includes four data: (1) a letter, which is identifies the research group; (2) the initial instant of the request; (3) the final instant of the request; (4) a real number, which represents the cost of the operation to be performed. The initial moments and final are integers (we will assume that the time frame in which we can use the microscope be divided into 1440 minutes). The program acquires data from standard input. The first line contains the number n of requests. Each subsequent line contains the four data related to a single request, in the order in which they are described above, and separated by spaces. Suppose the data is correct; in particular, that for each request they are worth (1) si < fi and (2) fi <1440. After calculating the solution, the program must print the selected request data, sorted according to the starting point, and the total cost of the solution. The exercise consists of a form of interval scheduling (or allocation of intervals). In the simple variant proposed here, the solution can be calculated by applying a greedy type algorithm, which at each step chooses, among the residual requests, the one with the minor end instant (excluding, of course, those not compatible with the requests already selected ). Example of input data format: 6 B 120 280 12.34 B 1100 1187 6.34 C 260 480 9.761 A 180 512 11.34 C 360 900 14.2 D 280 512 9.2 For these data, the suggested algorithm provides the solution (B 120 280 12.34) (D 280 512 9.2) (B 1100 1187 6.34) with a total value of 27.88. There is another acceptable solution of cardinality 3, formed by (B 120 280 12.34) (C 360 900 14.2) (B 1100 1187 6.34), with a value of 32.88. It is emphasized that the exercise does not require the determination of a maximum value solution.