(Analysis by Nick Wu)

In this problem, we have several lifeguards that we have hired for various time intervals. We have to fire one lifeguard while still covering as many intervals as possible.

Because there are a small number of lifeguards and the time intervals are relatively short, we can just try firing each one and keeping track of how many lifeguards are still working in each time interval.

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

int[] start = new int[n];
int[] end = new int[n];
for(int i = 0; i < n; i++) {
start[i] = Integer.parseInt(st.nextToken());
end[i] = Integer.parseInt(st.nextToken());
}

// figure out, for each time interval, how many lifeguards are covering it
int[] numCover = new int[1000];
for(int i = 0; i < n; i++) {
for(int t = start[i]; t < end[i]; t++) {
numCover[t]++;
}
}
int maxCover = 0;
for(int i = 0; i < n; i++) {
// we fire lifeguard i temporarily
for(int t = start[i]; t < end[i]; t++) {
numCover[t]--;
}
// count how many intervals are still covered
int covered = 0;
for(int t = 0; t < 1000; t++) {
if(numCover[t] > 0) {
covered++;
}
}
maxCover = Math.max(maxCover, covered);
// revert the firing
for(int t = start[i]; t < end[i]; t++) {
numCover[t]++;
}
}
pw.println(maxCover);
pw.close();
}
}