320SC留学生代做、代写Programming、代写Java/Python编程设计、代做c/c++语言-代写Python编程

Computer Science 320SC – (2019)

Programming Assignment 3

Due: Saturday, September 14th (11:57pm)

Requirements

This assignment requires you to write three efficient algorithms that processes intervals. At least two

of them should be implemented via some type of greedy algorithm. It is worth 5% of your total course

marks.

All three programs have the same input and output format. The input will begin with an integer

n ≤ 1000 denoting how many test cases. This is followed by n lines of an even number 2m of whitespace

separated integers:

a1 b2 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:

Determine the maximum number of non-overlapping intervals.

Problem 2:

Find the maximum number of intervals that overlap at a single point (on x-axis).

Problem 3:

Compute the largest contiguous interval obtained by taking a union of some of the input intervals.

Sample Input:

Submission

These problem requirements will be worth 2, 2 and 1 marks, respectively, on the computer science

automarker https://www.automarker.cs.auckland.ac.nz/. For this assignment you can use any

language supported on the automarker and can submit up to 8 times for each problem before occuring

a 20% penalty.