USACO Silver 2018 January - Lifeguards

Authors: Óscar Garries, Kevin Sheng, Nathan Wang

Official Analysis (Java)

C++

Implementation (With Sets)

#include <bits/stdc++.h>
using namespace std;
struct Event {
int time;
int cow_id;
bool is_start;
};
bool operator<(const Event &a, const Event &b) { return a.time < b.time; }

Another Implementation (No Sets)

#include <bits/stdc++.h>
using namespace std;
struct Cow {
int l, r;
};
bool operator<(const Cow &a, const Cow &b) { return a.l < b.l; }
int main() {

Java

Implementation

Lightly modified from the official editorial.

import java.io.*;
import java.util.*;
public class Lifeguards {
Code Snippet: Event Class (Click to expand)
public static void main(String[] args) throws IOException {
BufferedReader read =
new BufferedReader(new FileReader("lifeguards.in"));

Python

Code Snippet: Event Class (Click to expand)
with open("lifeguards.in") as read:
n = int(read.readline())
events = []
for i in range(n):
l, r = [int(i) for i in read.readline().split()]
# each cow interval can be represented by a start and end event
events.append(Event(l, i, True))
events.append(Event(r, i, False))

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!