USACO Lifeguards

USACO 2018 January Contest, Silver¶

Problem 1. Lifeguards¶

http://usaco.org/index.php?page=viewproblem2&cpid=786

In [1]:

# SAMPLE INPUT
#
# 3
# 5 9
# 1 4
# 3 7

In [2]:

fin = open("lifeguards.in", "r")
fout = open("lifeguards.out", "w")

# 1 <= N <= 100,000
N = int(fin.readline().strip())
#print(N)
Schedule = []
for i in range(N):
    s,t = map(int,fin.readline().split())
    #print(s,t)
    Schedule.append((s,i))
    Schedule.append((t,i))

Schedule.sort()
print(Schedule)

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

In [3]:

cover = 0
alone = [0]*N
last = 0
onduty = set()

for endpoint in Schedule:
    if (len(onduty) == 1):
        for loneguard in onduty:
            alone[loneguard] += endpoint[0] - last
    
    if (len(onduty) > 0): 
        cover += endpoint[0] - last

    if (endpoint[1] in onduty):
        onduty.remove(endpoint[1])
    else:
        onduty.add(endpoint[1])

    last = endpoint[0]
    
ans = 0
for item in alone:
    ans = max(ans, cover - item)

print(ans)
fout.write(str(ans)+"\n")
fout.close()

7