USACO Silver 2018 January - Lifeguards

C++

Implementation (With Sets)

Copy
#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)

Copy
#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.

Copy
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"));

		int n = Integer.parseInt(read.readLine());

Python

Copy
 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))