문제

성실한 농부 존은 시간을 효율적으로 관리해야 한다는 걸 깨달았다. 그는 N개의 해야할 일에 (1<=N<=1000) 숫자를 매겼다. (우유를 짜고, 마굿간을 치우고, 담장을 고치는 등의)

존의 시간을 효율적으로 관리하기 위해, 그는 끝내야만 하는 일 목록을 만들었다. 완성될 때 필요한 시간을 T_i(1<=T_i<=1,000) 라고 하며, 끝내야하는 시간을 S_i(1<=S_i<=1,000,000) 이라 한다. 농부 존은 하루의 시작을 t = 0으로 정했다. 그리고 일 할 때는 그 일을 마칠 때 까지 그 일만 한다.

존은 늦잠 자는 걸 좋아한다. 따라서 제 시간에 끝낼 수 있게 결정할 수 있는 한도에서 존이 가장 늦게 일어나도 되는 시간을 출력하라.

# 6068
import sys
input = lambda: sys.stdin.readline().strip()

n = int(input())
work = [list(map(int, input().split())) for _ in range(n)]

work.sort(key = lambda x:x[0])
work.sort(key = lambda x:x[1])

def check_work(arr, time):
    for a in arr:
        time += a[0]
        if time > a[1]:
            return False
    return True

def binary_search(arr, start, end):
    sleep = []
    while start <= end:
        mid = (start + end) // 2
        if check_work(arr, mid):
            sleep.append(mid)
            start = mid + 1
        else:
            end = mid - 1
            
    if len(sleep) == 0:
        return -1
    else:
        return max(sleep)

print(binary_search(work, 0, 1000000))

백준 6068 시간 관리하기