Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
Programming Assignment
Requirements
This assignment requires you to write five efficient algorithms that processes intervals. At least three of them should be implemented via some type of greedy algorithm. It is worth 5% of your total course marks.
All five programs have the same input and output format. The input will begin with an integer n ≤ 1000 denoting how many testcases. This is followed by n lines of an even number 2m of whitespace separated integers:
a1 b1 a2 b2 a3 b3 . . . am bm
Each pairs [ai , bi] denotes a closed interval where it is guaranteed that ai ≤ bi for 1 ≤ i ≤ m. The output will be a single integer per line denoting the answer to the following questions.
Problem 1:
Print the sum of the lengths of all intervals.
Problem 2:
Find the smallest gap length between any two non-overlapping intervals. If no gaps then output the range of the set.
Problem 3:
Determine the maximum number of non-overlapping intervals.
Problem 4:
Find the maximum number of intervals that overlap at a single point (on x-axis).
Problem 5:
Compute the largest contiguous interval obtained by taking a union of some of the input intervals.
Submission
These problem requirements will each be worth 1 marks. Sumbit diferent solutions to the computer science automarker https://www.automarker.cs.auckland.ac.nz/. For this assignment you need to use the Python programming language and can submit up to 8 times for each problem before occuring a 20% penalty.
Example Input/Output Input:
4
1 3 0 2 3 4
0 3 1 2 1 3 4 4
0 2 3 4 5 6 3 6 2 4
1 1 1 2 1 3 1 4 1 5
Output 1 |
Output 2 |
Output 3 |
Output 4 |
Output 5 |
5 |
1 |
2 |
2 |
4 |
6 |
1 |
2 |
3 |
3 |
9 |
1 |
3 |
3 |
6 |
10 |
4 |
1 |
5 |
4 |