서로 다른 점 10^5개가 주어질 때, 한 점이 다른 점을 좌표로 지배하면 두 입자가 상호작용해 하나가 사라질 수 있다. 남을 수 있는 최소 입자 수를 구한다.
어려움8정렬그리디배열수학아직 제출이 없습니다시간 제한1초메모리 제한512 MBQuarantined for their protection during an outbreak of COWVID-19, Farmer John's cows have come up with a new way to alleviate their boredom: studying advanced physics! In fact, the cows have even managed to discover a new subatomic particle, which they have named the "moo particle".
The cows are currently running an experiment involving N moo particles (1≤N≤105). Particle i has a "spin" described by two integers x_i and y_i in the range −109…109 inclusive. Sometimes two moo particles interact. This can happen to particles with spins (x_i,y_i) and (x_j,y_j) only if x_i≤x_j and y_i≤y_j. Under these conditions, it's possible that exactly one of these two particles may disappear (and nothing happens to the other particle). At any given time, at most one interaction will occur.
The cows want to know the minimum number of moo particles that may be left after some arbitrary sequence of interactions.
The first line contains a single integer N, the initial number of moo particles. Each of the next N lines contains two space-separated integers, indicating the spin of one particle. Each particle has a distinct spin.
A single integer, the smallest number of moo particles that may remain after some arbitrary sequence of interactions.