USACO 2018 January Contest Bronze Division - Lifeguards

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

We want to intersect the two rectangles and see if at least one sides of the intersection is equal to the entire rectangle's side, and from that point we have some casework we need to do.

Source codes

The source codes in C++ and Python can be seen below.

#include <fstream>
#include <vector>

using namespace std;

int main() {
    ifstream cin("lifeguards.in");
    ofstream cout("lifeguards.out");

    int n;
    cin >> n;
    vector<int> start(n), end(n);
    for (int i = 0; i < n; i++) {
        cin >> start[i] >> end[i];
    }

    vector<int> numCover(1000, 0);
    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++) {
        for (int t = start[i]; t < end[i]; t++) {
            numCover[t]--;
        }
        int covered = 0;
        for (int t = 0; t < 1000; t++) {
            if(numCover[t] > 0) {
                covered++;
            }
        }
        maxCover = max(maxCover, covered);
        for (int t = start[i]; t < end[i]; t++) {
            numCover[t]++;
        }
    }

    cout << maxCover << '\n';

    return 0;
}

with open("lifeguards.in", "r") as fin:
    tokens = fin.read().split()

n = int(tokens[0])
start = [0] * n
end = [0] * n
index = 1
for i in range(n):
    start[i] = int(tokens[index])
    index += 1
    end[i] = int(tokens[index])
    index += 1

numCover = [0] * 1000
for i in range(n):
    for t in range(start[i], end[i]):
        numCover[t] += 1

maxCover = 0
for i in range(n):
    for t in range(start[i], end[i]):
        numCover[t] -= 1
    covered = 0
    for t in range(1000):
        if numCover[t] > 0:
            covered += 1
    maxCover = max(maxCover, covered)
    for t in range(start[i], end[i]):
        numCover[t] += 1

with open("lifeguards.out", "w") as fout:
    fout.write(str(maxCover) + "\n")