Your task is to: 1) Give the algorithm (step by step) and explain/justify why it takes about 2 time complexity. 2) Write a program called contactTracing.java, which implements the algorithm in 1. a) Ask the user to input the number of babies in the creche b) Followed by arrival and departure times (separated by ,) for each baby c) Store these data into a data structure d) Apply algorithm 1 on the data structure and determine the pairs

Sample Input How many pairs of baby: 5 Give the times of arrival (i) and departure (j), e.g.: 2,4 2,4 Give the times of arrival (i) and departure (j), e.g.: 2,4 3,6 Give the times of arrival (i) and departure (j), e.g.: 2,4 8,9 Give the times of arrival (i) and departure (j), e.g.: 2,4 10,11 Give the times of arrival (i) and departure (j), e.g.: 2,4 7,11

Sample Output The distinct pairs of babies who are at the crche simultaneously are (1, 2) (3, 5) (4, 5)

Creche Contact Tracing Consider a crche that experienced a sudden outbreak of an infection. This infection caused n number of babies to get sick at different periods (NB: n is an integer). For each i=1,,n, a baby that enters the crche at time ai leaves at time di>=ai, suppose we are interested in knowing how many distinct pairs of babies are ever at the crche at the same time? (NB: pair (i, j) is the same as pair (j,i) ). For example, consider Table 2: Suppose there are 5 babies with the following arrival and departure times: Table2: Rahies Arrival and Denarture Times at the Crche In table 2 , clearly, Babyl arrived at time 2 and left at time 4, but note that Baby 2 also arrived at time 3, which is before Baby 1 left the crche. Hence, the number of distinct pairs of babies who are at the crche simultaneously is three: These pairs are {(1,2),(4,5),(3,5)} Considering the input (a1,d1)(a2,d2)(an,dn) as earlier described, there is a straightforward algorithm that takes about n2 time complexity to compute the number of pairs of babies that are at the crche at the same time