まず、人 \(i\) と人 \(j\) \((i \neq j)\) が同時に凧を揚げられる条件を言い換えて整理すると次のようになります。

• 次の \(2\) つの条件のどちらか一方が成り立つ。\(\cdots (\ast)\)
  • \(A_i \lt A_j\) かつ \(B_i \lt B_j\)
  • \(A_j \lt A_i\) かつ \(B_j \lt B_i\)

よって、\(\lbrace 1,2,\dots, N \rbrace\) の部分集合 \(S\) であって \(S\) の相異なる元 \(i,j\) が \((\ast)\) を満たすもののうち最大の \(S\) のサイズを求める問題を解けばよいことが確認できました。

この問題は LIS(Longest Increasing Subsequence, 最長増加部分列) を計算する問題に帰着することができます。
LIS とは、単調増加である数列の部分列のうち最長である列のことをいいます。つまり、数列 \(C=(c_1,c_2,\dots,c_N)\) の LIS は \(\lbrace 1,2,\dots, N \rbrace\) の部分集合 \(S\) であって \(S\) の相異なる元 \(i,j\) が以下の条件を満たすもののうちサイズ最大のものです。

• 次の \(2\) つの条件のうちどちらか一方が成り立つ。
  • \(i \lt j\) かつ \(c_i \lt c_j\)
  • \(j \lt i\) かつ \(c_j \lt c_i\)

この条件は \((\ast)\) に類似しているので、 \(A_i\) を \(i\) に、\(B_i\) を \(c_i\) に対応させれば直感的には等価な問題になっていそうです。つまり、元の問題は \((A_i, B_i)\) の列を \(A_i\) 昇順に並べ替えた後に \(B\) を取り出してできる列の LIS が答えになりそうであると直感的に考えられます。
ただしこのままでは \(A_i\) のタイブレークに注意する必要があります。例えば \((A_1, B_1)=(1,2), (A_2,B_2)=(1,3)\) である時に \(S =\lbrace 1,2 \rbrace\) は選べませんが、上記の LIS への言い換えでは選べることになってしまいます。 解決策は簡単で、以下の方法を用いればよいです：

• \((A_i, B_i)\) の列を \(A_i\) 昇順 に並べ替える。ただし \(A\) の値が一致する時は \(B_i\) 降順 で並べ替える。

この方法でタイブレークに関する問題が解決していることが確認できます。よって元の問題を LIS に正しく帰着することができました。

LIS の計算方法については「最長増加部分列」などの単語で検索すればいくつかの解説記事が出て来るのでここでは説明を省略しますが、動的計画法により \(\mathrm{O}(N \log N)\) で LIS の長さを計算することができて、これは十分高速です。

• 実装例(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";
}