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)

Transcribed Image Text:

Consider a crèche 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 crèche at time a, leaves at time d₁>= a₁, suppose we are interested in knowing how many distinct pairs of babies are ever at the crèche 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 Crèche 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 crèche. Hence, the number of distinct pairs of babies who are at the crèche 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 crèche at the same time. Consider a crèche 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 crèche at time a, leaves at time d₁>= a₁, suppose we are interested in knowing how many distinct pairs of babies are ever at the crèche 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 Crèche 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 crèche. Hence, the number of distinct pairs of babies who are at the crèche 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 crèche at the same time.

Answer rating: 100% (QA)

Algorithm Create an empty list to store baby arrival and departure times as pairs Ask the user for t... View the full answer