(Analysis by Nick Wu)

This problem gives us the speed limit along a 100 mile segment of road and the speed that Bessie traveled through each section. Our job is to figure out the maximum amount that Bessie was over the speed limit at any point during her journey.

One simple approach is to break up the road into 100 sections, each one mile long. We can then "unroll" the input to determine the speed limit of each 1 mile section of road and Bessie's speed over that section. After we do that, we can loop over the 100 sections and compute the maximum over the speed limit Bessie is for any section.

Here is my code demonstrating this solution.

import java.io.*;
import java.util.*;
public class speeding {
public static void main(String[] args) throws IOException {
// initialize file I/O
PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("speeding.out")));

// read in the first line, store n and m
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());

// speedLimits[K] will store the speed limit of the section of road
// starting at mile K and ending at mile K+1.
int[] speedLimits = new int[100];
int currentMile = 0;

for(int i = 0; i < n; i++) {
// read in length and speed limit of segment i of the road
st = new StringTokenizer(br.readLine());
int lengthOfSegment = Integer.parseInt(st.nextToken());
int speedLimit = Integer.parseInt(st.nextToken());
// update the speed limit for the given segment
for(int j = 0; j < lengthOfSegment; j++) {
speedLimits[currentMile] = speedLimit;
currentMile++;
}
}

// travelSpeed[K] will store the speed that Bessie traveled at for
// the section of road starting at mile K and ending at mile K+1.
int[] travelSpeed = new int[100];
currentMile = 0;
for(int i = 0; i < m; i++) {
// read in length and speed that Bessie drove
st = new StringTokenizer(br.readLine());
int lengthOfSegment = Integer.parseInt(st.nextToken());
int speedLimit = Integer.parseInt(st.nextToken());
// update the speed traveled for the given segment
for(int j = 0; j < lengthOfSegment; j++) {
travelSpeed[currentMile] = speedLimit;
currentMile++;
}
}

// maxOver will store the maximum amount over the speed limit that Bessie traveled.
int maxOver = 0;
for(int i = 0; i < 100; i++) {
// compute the amount over the speed limit Bessie traveled
int amountExceeded = travelSpeed[i] - speedLimits[i];
// update maxOver if we have exceeded it
if(amountExceeded > maxOver) {
maxOver = amountExceeded;
}
}

// print the answer!
pw.println(maxOver);

// close output stream
pw.close();
}
}