Computer Science 320 S2 – (2024)
Programming Assignment 2
Due: August 9th (11:59pm)
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 |
标签：Computer,Science,number,320,intervals,input,Output,Problem From： https://www.cnblogs.com/vx-codehelp/p/18354726