문제

아 과제 하기 싫다. 아무 것도 안 하고 싶다. 더 적극적이고 격렬하게 아무 것도 안 하고 싶다.

있잖아. 내가 아까 책상에다가 n개의 과제 목록을 적어놨어. 각각의 과제 i는 di 일이 걸리고, 오늘로부터 ti 일 안에 끝내야 해. 그러니까 오늘이 0일이면, ti일이 끝나기 전에 제출이야. 과제는 한번 시작하면 쉬지 않고 계속해야 해. 안 그러면 머리 아파 지거든.

근데 있잖아. 내가 지금 너무, 너무 아무 것도 안 하고 싶어. 그래서 오늘은 아무 것도 안 할 거야. 더 중요한 게 뭔지 알아? 사실 나 내일도, 모레도, 아무 것도 안 하고 싶어. 한 며칠 동안은 계속 아무 것도 안하려고. 아. 과제가 있을 때 내가 내일부터 연속으로 최대 며칠동안 놀 수 있는지 궁금하다. 궁금하긴 한데, 난 아무 것도 안 하고 싶어.

좋은 생각이 났다. 너희가 이걸 대신 구해주면, 내가 너희의 맞은 문제 수를 하나 올려줄게.

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

# 공부 시작 날 : 이진 탐색을 이용
# 시간복잡도 : O(N + logN) => O(N)

n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)]
arr.sort(key = lambda x : x[0])
arr.sort(key = lambda x : x[1])

def rest_day(arr, day):
    # O(N)
    for i in range(len(arr)):
        day += arr[i][0]
        if day > arr[i][1]:
            return False
    return True

def binary(arr, start, end):
    # O(logN)
    mid = 0
    while start <= end:
        mid = (start + end) // 2
        if rest_day(arr, mid):
            if start == mid:
                break
            start = mid
        else:
            end = mid
    return mid

print(binary(arr, 0, 10**9))

백준 7983 내일 할거야