Choisir son manteau

Choisir un manteau pour les vacances est toujours difficile, surtout lorsque l'on ne sait pas encore où l'on part. En effet chaque manteau est adapté à une certaine plage de température et vous aimeriez bien choisir un manteau qui s'adaptera à vos besoins.

Vous voilà dans un vaste magasin de manteaux, un peu perdu dans l'énorme choix proposé. Pour chacun des manteaux du magasin, vous connaissez l'intervalle de température qui lui correspond.

Avec votre logique impassible, vous décidez d'inventer un critère qui vous aidera à choisir votre manteau : Le niveau d'un manteau sera défini comme le nombre d'autres manteaux du magasin dont l'intervalle de température est contenu dans l'intervalle de celui-ci.

Vous décidez de sortir votre ordinateur et d'écrire un programme qui déterminera le niveau maximal que l'on peut trouver.

Limites de temps et de mémoire (Python)

  • Temps : 2 s sur une machine à 1 GHz.
  • Mémoire : 8 000 ko.

Contraintes

  • 1 <= nbManteaux <= 20 000.
  • 0 <= temperatureinf, temperaturesup <= 500 000 000, l'intervalle de température d'un manteau.

Entrée

Sur la première ligne de l'entrée, votre programme lira un unique entier : nbManteaux, le nombre de manteaux du magasin.

Il lira ensuite nbManteaux lignes contenant chacune deux entiers indiquant l'intervalle de température d'un manteau.

Sortie

Votre programme affichera un unique entier : le niveau maximal d'un manteau.

Exemple

entrée :

8
1 3
2 5
5 8
3 6
2 5
3 8
3 6
3 8

sortie :

4

Commentaires

Dans l'exemple présenté, les niveaux des manteaux sont, dans l'ordre : 0, 1, 0, 1, 1, 4, 1, 4.

Le résultat à afficher est donc 4.

Si vous ne passez pas en temps les derniers tests, c'est que votre algorithme est trop lent. A vous de l'améliorer, par vous-même.


Source : http://www.france-ioi.org/