수업

• 키가 큰 사람부터 배정하도록 하자. i번 사람을 배정할 때에는, 이전에 배정된 사람들은 모두 자신보다 키가 큰 사람들이므로, 이미 만들어진 그룹들중에서 크기가 k_i 보다 작은 팀에 배정하거나, 새로운 팀을 만들어 배정하는 것만 가능하다.
• 배정할 수 있는 팀이 여러개일때에는 가장 크기가 큰 팀을 선택해서 배정하는 그리디 전략을 사용한다. 예를 들어, 이전에 이미 크기가 2와 1인 두개의 팀이 있고 두군데 모두 들어갈 수 있을때, 팀의 크기를 3,1 로 만드는 것과, 팀의 크기를 2,2로 만드는 것 중에서, 뒷 사람에게 더 많은 선택지를 주는 것은 첫번째 전략이고, 일반화하면 크기가 작은 그룹들을 최대한 유지하는 것이 우위 전략이 된다. 엄밀한 증명은 아니긴 하다만..
• 이제 이 전략을 구현하기만 하면 된다. 필요한 연산은, 크기가 k미만인 그룹들 중 가장 큰 크기의 그룹을 찾는 것, 그룹의 크기를 업데이트 하는 것, 크기 1짜리 그룹을 추가하는 것이다. 일반적으로는 Ordered Set을 이용하면 find_lt, delete&add, add로 세가지를 모두 O(logn)에 처리할 수 있다. n개의 원소에 대해서 저 작업들을 처리하고 난 뒤에 그룹의 개수를 출력하면 된다
• 하지만 이 문제에서는 좀더 간단한 방법이 존재한다. 원소들을 수정하는 연산이, 존재하는 값에 1을 더하는것과, 1을 추가하는 것뿐인데, 이것은 그냥 값들을 정렬해서 갖고 있더라도 정렬상태를 유지한채로 저 연산들을 적용할수 있다. 따라서 복잡한 자료구조 없이, 그냥 정렬된 리스트와 이분탐색만으로 필요한 연산들을 모두 처리할수 있다. find_lt는 O(logn), 원소 수정은 O(1)에 할수 있다.
• 구현상 약간의 트릭이 필요하기는 하다. 1을 추가하는 연산을 O(1)에 처리하기 위해서는 값들이 내림차순으로 정렬되어있어야 하는데, builtin bisect 함수는 오름차순으로 정렬된 리스트에 대해서만 동작한다. 그래서, 리스트에는 그룹의 크기들을 그대로 저장하는 대신 음수로 변환해서 저장하고, 거기에 맞춰서 연산들을 처리하는 식으로 하면 된다.
  • 또는 bisect 함수를 호출할때 key 함수에 operator.neg를 넘겨주는 방법도 있긴 하다.
• O(logn) 연산을 n번 하므로 총 시간복잡도는 O(nlogn)

"""Solution code for "BOJ 19700. 수업".

- Problem link: https://www.acmicpc.net/problem/19700
- Solution link: http://www.teferi.net/ps/problems/boj/19700

Tags: [binary search]
"""

import sys
import bisect


def main():
    N = int(sys.stdin.readline())
    h, k = [], []
    for _ in range(N):
        h_i, k_i = [int(x) for x in sys.stdin.readline().split()]
        h.append(h_i)
        k.append(k_i)

    group_sizes = []
    sorted_inds = sorted(range(N), key=h.__getitem__, reverse=True)
    for i in sorted_inds:
        pos = bisect.bisect_right(group_sizes, -k[i])
        if pos == len(group_sizes):
            group_sizes.append(-1)
        else:
            group_sizes[pos] -= 1

    print(len(group_sizes))


if __name__ == '__main__':
    main()