USACO 2018 January Contest Silver Division - Lifeguards

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

Loop through all critical points (points where a lifeguard starts or ends their shift) and check the running number of lifeguards operating at that time. If the count is one, then that is the unique area owned by a specific lifeguard, and removing that contributes to removing an area from the total area (shared area has one or more lifeguards to cover) find the minimum over all individual areas and subtract it from the total.

Source code

The source code in C++ can be seen below.

#include <bits/stdc++.h>
using namespace std;

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

    int n, i;
    cin >> n;

    vector<pair<int, int>> shift(n + 2);
    for (i = 1; i <= n; i++) {
        cin >> shift[i].first >> shift[i].second;
    }

    shift[n + 1].first = shift[n + 1].second = INT_MAX;  // took some time to figure out I needed to add this
    sort(shift.begin(), shift.end());

    pair<int, int> disjShift = {INT_MIN, INT_MIN};
    int ans = 0, removeTime = INT_MAX, endTime = INT_MIN;

    for (i = 1; i <= n; i++) {
        disjShift = {max(shift[i].first, shift[i - 1].second), min(shift[i].second, shift[i + 1].first)};
        endTime = max(endTime, disjShift.first);

        if (disjShift.first < disjShift.second) {
            removeTime = min(removeTime, disjShift.second - disjShift.first);
        } 
        else {
            removeTime = 0;
        }

        if (endTime < shift[i].second) {
            ans += shift[i].second - endTime;
        }
    }

    cout << (ans - removeTime);
    return 0;
}