10. Union of intervals
Deadline: 2022-04-27 24:00
Given \(N\) closed intervals \([A_1, B_1], [A_2, B_2], \ldots [A_N,
B_N]\), where \(A_i\) and \(B_i\) are natural numbers. We want to
dermine the total length of the intervals, precisely the measure of
the domain \[\bigcup_{i = 1}^N [A_i, B_i].\]
We provide an
example
program
interval.py that reads
the intervals from the file named in the command line argument.
- Every line of the input file contains two numbers \(A\) and \(B\), the
starting and the endpoint of an interval, where \(0 < A <
B\).
- In the
program interval.py the
function read_intervals()
reads the intervals and return a list of
Interval objects. The
class Interval has two
attributes:
start and
end, these are the
bounderies of the interval.
- Complete the code of the
measure() function, such
that it calculates the total length of the domain covered by the
given intervals, that is the
measure of the union of these intervals. Let's try to achieve
the efficient algorithm of \(O(N \log N)\) steps.
- Try the program on the following inputs. The efficient algorithm
of \(O(N \log N)\) steps runs on each of the following inputs in a
few seconds. In addition to the inputs, we have given in the table
the total length of the intervals.