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 crèche simultaneously are
(1, 2) (3, 5) (4, 5)

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 a, leaves at time d>= a, 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: Babies Arrival and Departure Times at the Crche Baby Arrival time (a) 1 2 3 4 5 2 3 8 10 7 Departure time (d) 4 6 9 11 11 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 I 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 (a, d) (a, d)... (an, dn) as earlier described, there is a straightforward algorithm that takes about n time complexity to compute the number of pairs of babies that are at the crche at the same time.