Challenge Lab 8: Heaps and Hashes

Introduction

In this lab, you’ll be working with heaps and hashing. You will only need to complete the first problem to get credit, but we added the second question to give you some practice with using APIs and help you see practical applications of hashing!

Problem 1: Flight

Imagine that we have a list of every commercial airline flight that has ever been taken, stored as an ArrayList. Each Flight object stores a flight start time, a flight ending time, and a number of passengers. These values are all stored as ints.

Each flight’s start time and end time represents the number of minutes that have elapsed in the Pacific Time Zone since midnight on January 1st, 1914, which was the first day of commercial air travel.

For example, a flight taking off at 2:02 PM on March 6th, 1917 and landing at 3:03 PM the same day carrying 30 passengers would have takeoff time 1,671,243, landing time 1,671,304, and number of passengers 30.

Implement an algorithm for finding the largest number of people that have ever been in flight at once.

Your algorithm must run in time, where is the number of total commercial flights ever taken. Your algorithm must not have a runtime that is explicitly dependent on the number of minutes since January 1st, 1914, i.e. you can’t just consider each minute since that day and count the number of passengers from each minute and return the max.

Your algorithm may use any data structure that we’ve covered thus far, though we recommend doing it with a java.util.PriorityQueue.

Comparators & Lambdas

You may need to use comparators in your solution for comparing objects. You can construct a concrete class (which can be somewhat verbose) or use lambda functions instead. The syntax for declaring a lambda for a comparator is:

    Comparator<Type> function = (Type arg1, Type arg2) -> (...);
    Comparator<Type> functionEquivalent = (arg1, arg2) -> (...);

where (…) is your desired return value that can use arguments arg1 and arg2.

Examples:

        Comparator<Integer> intComparator = (i, j) -> i - j;
        Comparator<Integer> intComparatorEquivalent = (i, j) -> {
          int diff = i - j;
          return diff;
        };

You may also want to look into the function Integer.compare. Note: lambdas will not be in scope for this course (i.e. not tested).

Your Task

Write the class FlightSolver that has the following methods:

Problem 2: Rabin-Karp Algorithm (Extra)

The Rabin-Karp algorithm is a string-searching algorithm that “uses hashing to find any one of a set of pattern strings in a text”. One practical application is detecting plagiarism. The algorithm takes time, for text of length and a pattern string of length .

Your Task

Submission

Submit your solution to part 1 (and optionally part 2) to Gradescope.