B - 区間スケジューリング問題

B - 区間スケジューリング問題

O(N)

import sys
import math
import heapq
import itertools
from collections import deque
from functools import reduce

# main
def main():
    N = int(input())
    BA = []
    for i in range(N):
        a, b = list(map(int, input().split()))
        BA.append([b, a])
    BA.sort()
    ans = 0
    last = 0
    for b, a in BA:
        if last < a:
            ans += 1
            last = b
    print(ans)

# エントリポイント
if __name__ == '__main__':
    main()