You are in a bit of a jam. The head of the local police force has been ordered to discover the number of people who have been speeding on a local road. He set up two radar guns at each end of the road, and recorded the times that the vehicles entered the road, and the times at which they exited the road. Thus, he could easily determine how many people were speeding and collect fines from them.
The police chief's plan fell through, though, when he was fired for illegal gambling involving squirrels. On his way out the door, he scrambled the times so that you no longer know which entering time belongs to which exit time.
You need to solve this issue so that you can plan this year's budget. You have enterTimes and exitTimes, which correspond to times (in seconds) in which cars entered and exited the road, respectively. You also know speedTime; a car is considered speeding if it takes less than speedTime seconds to travel down the road. No matter how quickly the cars are speeding, it always takes at least 1 second for a car to travel down the road.
You must select a matching of enterTimes and exitTimes, such that each car exits the road at a time later than when it enters, and each element of enterTimes and exitTimes is used exactly once. Once you have done this, you will collect fines from those cars that were speeding. If a speeding car took T seconds to travel on the road, then you will collect (speedTime-T)^2 dollars from the car (up to a maximum of fineCap dollars); if a car was not speeding (i.e., it took at least speedTime seconds to travel on the road), you can collect no fine from that car.
Since you can't exactly determine the total amount of money that you should collect from all of the cars, you instead want to determine the minimum and maximum sums of money that you can collect. You will return a int[] containing two elements, the first being the minimum sum that can be collected, and the second containing the maximum sum. If the data could not be obtained by the radar guns, you are to return an empty int[].
|