First of all, persons \(i\) and \(j\) \((i \neq j)\) can fly kites simultaneously if and only if:

• One of the following holds: \(\cdots (\ast)\)
  • \(A_i \lt A_j\) and \(B_i \lt B_j\).
  • \(A_j \lt A_i\) and \(B_j \lt B_i\).

Thus, the problem is reduced to finding the maximum size of a subset \(S\) of \(\lbrace 1,2,\dots, N \rbrace\), where any pair of distinct elements \(i\) and \(j\) of \(S\) satisfy \((\ast)\).

This is boiled down to finding a LIS (Longest Increasing Subsequence).
A LIS is a monotonically increasing subsequence with the maximum length. That is, a LIS of a sequence \(C=(c_1,c_2,\dots,c_N)\) is a subset \(S\) of \(\lbrace 1,2,\dots, N \rbrace\) with the maximum size, such that any pair of distinct elements of \(i\) and \(j\) of \(S\) satisfy:

• One of the following holds:
  • \(i \lt j\) and \(c_i \lt c_j\)
  • \(j \lt i\) and \(c_j \lt c_i\)

As this condition is similar to \((\ast)\), they seem equivalent by corresponding \(A_i\) to \(i\) and \(B_i\) to \(c_i\). In other words, it appears that the answer to the original problem is the length of a LIS of a sequence that is obtained by sorting the sequence of \((A_i, B_i)\) in ascending order of \(A\) and extracting \(B\).
However, you need to be careful of tie-breaking of \(A_i\). For example, if \((A_1, B_1)=(1,2)\) and \((A_2,B_2)=(1,3)\), we cannot choose \(S =\lbrace 1,2 \rbrace\), but the above LIS-representation of the problem allows to choose that way. The solution is simple; we adopt the following trick:

• Sort the sequence of \((A_i, B_i)\) in ascending order of \(A_i\). If the values of \(A\) coincide, sort them in descending order of \(B_i\).

One can assert that this trick resolves the issue on tie-breaking. Thus, the problem has been successfully boiled down to a LIS problem.

We omit the explanation on how to find a LIS as we can find several articles regarding the algorithm on the Internet. In fact, a dynamic programming (DP) allows to find the length of a LIS in \(\mathrm{O}(N \log N)\) time, which is fast enough.

• Sample code (C++)

#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int N;
  cin >> N;
  vector<pair<int, int>> AB(N);
  for (auto& [a, b] : AB) cin >> a >> b;
  sort(begin(AB), end(AB), [&](auto& l, auto& r) {
    if (l.first == r.first) return l.second > r.second;
    return l.first < r.first;
  });
  vector<int> dp;
  for (auto& [_, b] : AB) {
    int i = lower_bound(begin(dp), end(dp), b) - begin(dp);
    if (i == (int)dp.size()) {
      dp.push_back(b);
    } else {
      dp[i] = b;
    }
  }
  cout << dp.size() << "\n";
}