HW2

Goal: To exercise designing greedy algorithms.

#1

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

For example:
Given array A = [2,3,1,1,4]

The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

Write code to solve this problem. Your code should run as follows:

$java Jump 2 3 1 1 4
2
$java Jump 2 3 1 1 1 2 1
4

#2

Given a collection of intervals, merge all overlapping intervals.

For example,

Given [1,3],[2,6],[8,10],[15,18]

return [1,6],[8,10],[15,18].

Write code to solve this problem. Your code should run as follows:

$java Merge 1 3 2 6 8 10 15 18
[1,6],[8,10],[15,18]

#3

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

Write code to solve this problem. Your code should run as follows. Take in pairs that represent the given intervals followed by the interval to insert.

//Given [1,3],[6,9], insert and merge [2,5]
$java InsertAndMerge 1 3 6 9 2 5
[1,5],[6,9]

//Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9]
$java InsertAndMerge 1 2 3 5 6 7 8 10 12 16 4 9
[1,2],[3,10],[12,16]

#4

Implement interval partitioning. Goal: find minimum number of classrooms to schedule all lectures so that no two lectures occur at the same time in the same room.

For example given three lectures by start and end time: [1,3], [6,9], [2,5] assign them to the minimum number of rooms. [1,3],[6,9] can be held in the same room but [2,5] requires another room to be allocated.

Write code to solve this problem. Your code should run as follows:

//Given [1,3], [6,9], [2,5]
$java IntervalPartition 1 3 6 9 2 5
Room 1: [1,3],[6,9]
Room 2: [2,5]

//Given [1,3],[1,7],[1,3],[4,7],[4,10]
$java IntervalPartition 1 3 1 7 1 3 4 7 4 10
Room 1: [1,3],[4,10]
Room 2: [1,7]
Room 3: [1,3],[4,7]

Due: 6/16 @5pm. Submit the code to users in .java files and any discussion in a memo.txt.

Grading
9 Points: All questions correct
1 Points: How easy to grade