Introduction
The hot new Cal startup AirBearsnBeds has hired you to create an algorithm to help them place their customers in the best possible homes to improve their experience. They are currently in their alpha stage so their only customers (for now) are bears. Now, a little known fact about bears is that they are very, very picky about their bed sizes: they do not like their beds too big or too little - they like them just right. Bears are also sensitive creatures who don’t like being compared to other bears, but they are perfectly fine with trying out beds.
The Problem
Given a list of Bears with unique but unknown sizes and a list of Beds with corresponding but also unknown sizes (not necessarily in the same order), return a list of Bears and a list of Beds such that that the \(i\)th Bear in your returned list of Bears is the same size as the \(i\)th Bed in your returned list of Beds. Bears can only be compared to Beds and we can get feedback on if the Bed is too large, too small, or just right. In addition, Beds can only be compared to Bears and we can get feedback if the Bear is too large for it, too small for it, or just right for it.
Constraints
Your algorithm should run in \(O(N\log N)\) time. It may be helpful to figure out the naive \(O(N^2)\) solution first and then work from there.
Provided Files
Bear.java: A Bear object that is Comparable to Beds.Bed.java: A Bed object that is Comparable to Bears.HiddenComparable.java: Used to implement Bears and Beds. You should not need to use this file or its method at all.Pair.java: A utility class that represents a two-item tuple. This is useful if you want to return two items in a function call. You don’t have to use this but you are free to.BnBSolver.java: Your solution to this problem should be implemented in here. Do not change the provided method headers, but you may add extra methods and attributes.BnBSolverTests.java: Provided tests.BnBSolverTimingTests.java: Visualizes the runtime of your solver compared to other algorithms that run in \(\Theta(N^2)\) and \(\Theta(N\log N)\) time.
Submission
As always, submit your solution to Gradescope.