Lifeguards Java

USACO 2018 January Contest, Silver¶

Problem 1: Lifeguards¶

The following java code is based on the official solution:

http://www.usaco.org/current/data/sol_lifeguards_silver_jan18.html

---

import java.util.*;

public class lifeguards5 {

    public static void main(String[] args) {

        Set<Integer> myset = new HashSet<Integer>();
        List<State> mylist = new ArrayList<State>();

        // Hardcoded Input Data
        // Normally this would be read from a file in a loop
        int n=3;
        int i=0;
        int start = 5;
        int end = 9;
        mylist.add(new State(start,i));
        mylist.add(new State(end, i));
        i=1;
        start = 1;
        end = 4;
        mylist.add(new State(start,i));
        mylist.add(new State(end, i));
        i=2;
        start = 3;
        end = 7;
        mylist.add(new State(start,i));
        mylist.add(new State(end, i));

        System.out.println(mylist.toString());
        Collections.sort(mylist);
        System.out.println(mylist.toString());

        int coverage = 0;
        int[] solo = new int[n];
        int last = 0;

        for(State out: mylist) {
            if(myset.size() == 1) {
                solo[myset.iterator().next()] += out.time - last;
            }
            if(!myset.isEmpty()) {
                coverage += out.time - last;
            }
            if(myset.contains(out.index)) {
                myset.remove(out.index);
            }
            else {
                myset.add(out.index);
            }
            last = out.time;
        }

        int ret = 0;
        for(int out: solo) {
            ret = Math.max(ret, coverage - out);
        }
        System.out.println(ret);
    }

    static class State implements Comparable<State> {
        public int time, index;
        public State(int a, int b) {
            time=a;
            index=b;
        }
        public int compareTo(State s) {
            return time - s.time;
        }
        public String toString() {
            return "State(" + time + "," + index + ")";
        }
    }
}

---

[State(5,0), State(9,0), State(1,1), State(4,1), State(3,2), State(7,2)]
[State(1,1), State(3,2), State(4,1), State(5,0), State(7,2), State(9,0)]
7