Kite

Análisis oficial (C++) 

Explicación

Cada persona $i$ corresponde a un segmento de $(A_i, 0)$ a $(B_i, 1)$. Notamos que dos segmentos no se tocan si y solo si $A_i < A_j \iff B_i < B_j$, donde compartir un extremo cuenta como tocarse. Así, queremos el mayor subconjunto de índices en el que ambas coordenadas son simultáneamente estrictamente crecientes.

Podemos ordenar las personas por $A_i$ creciente, desempate por $B_i$ decreciente. Tras ordenar, cualquier subsecuencia que elijamos ya tendrá $A$ en orden no decreciente. Notamos que el desempate decreciente en $B$ asegura que elegir dos entradas con el mismo $A$ violaría que $B$ sea estrictamente creciente, ya que sus valores de $B$ aparecen en orden decreciente. Por lo tanto, podemos reducir el problema a hallar la longitud de la LIS estricta de la secuencia $B$ resultante.

Implementación

Complejidad temporal: $\mathcal{O}(N \log N)$

#include <bits/stdc++.h>
using namespace std;
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(false);
 
	int n;
	cin >> n;
	vector<pair<int, int>> p(n);
	for (auto &[a, b] : p) { cin >> a >> b; }
 
	sort(p.begin(), p.end(), [](const auto &x, const auto &y) {
		return x.first != y.first ? x.first < y.first : x.second > y.second;
	});
 
	vector<int> dp;
	for (auto &[a, b] : p) {
		auto it = lower_bound(dp.begin(), dp.end(), b);
		if (it == dp.end()) dp.push_back(b);
		else *it = b;
	}
 
	cout << dp.size() << '\n';
}