Bonjour,
J'aimerais une explication sur des solutions d'un problème sur France IOI.
Le problème : http://www.france-ioi.org/algo/task.php?idChapter=671&iOrder=3

Une solution trouvée sur ce poste que je ne comprends pas : le poste -> https://openclassrooms.com/forum/sujet/choisir-son-manteau.
La solution un peu améliorée:

import sys
def main():
    N = int(input())
    manteaux = [tuple(map(int, sys.stdin.readline().split())) for _ in range(N)]
    manteaux = dict(enumerate(sorted(manteaux, key=lambda x: (x[0], -x[1]))))
    manteaux = sorted(manteaux, key=lambda x: (-manteaux[x][1], manteaux[x][0]))
    print(N - min(i + manteaux[i] for i in range(N)) - 1)
main()

Je n'arrive pas à comprendre la réflexion qu'il y a derrière.

Le code de solution écrit par France IOI que je ne comprends pas non plus:

from sys import stdin
from operator import itemgetter
  
def main():
   nbManteaux = int(input())
   manteaux = [
      (tuple(map(int,intervalle.split())),manteau)
      for manteau,intervalle in zip(range(nbManteaux),stdin)]
   manteaux = [(debut,-fin,manteau) for (debut,fin),manteau in manteaux]
    
   manteaux.sort()
   parDebut = [None]*nbManteaux
   for position,(_,_,manteau) in enumerate(manteaux):
      parDebut[manteau] = position
       
   manteaux.sort(key=itemgetter(1,0,2))
   parFin = [None]*nbManteaux
   for position,(_,_,manteau) in enumerate(manteaux):
      parFin[manteau] = position
    
   INFINI = 1000*1000*1000
   sommePosMin = INFINI
   for posDebut,posFin in zip(parDebut,parFin):
      sommePosMin = min(sommePosMin,posDebut+posFin)
   print(nbManteaux-1-sommePosMin)
 
main()

Et dernier point, ce code qui est aussi dans le lien posté, qui est plus rapide que les 2 autres sur les tests de France IOI mais je ne me trompe pas en disant qu'il est plus rapide seulement puisque aucun cas extrême n'est proposé ? ça reste du O(n2) donc si on a 20 000 manteaux avec aucune plage qui se chevauche il va être très lent.

import sys
def main():
    z = [tuple(map(int, sys.stdin.readline().split())) for _ in range(int(input()))]
    m = 0
    z.sort(key=lambda x: x[1] - x[0])
    qgr = 0
    while qgr < len(z):
        mag = len(z)
        aw, ah = z.pop()
        z = [i for i in z if not (i[0] >= aw and i[1] <= ah)]
        if mag - len(z) > qgr: qgr = mag - len(z)
    print(qgr - 1)
main()

Merci

up

J'explique le deuxieme qui est le plus facile à suivre. Le premier fait grosso modo la même chose écrit différemment, le troisième j'ai la flemme

def main(): nbManteaux = int(input()) manteaux = [ (tuple(map(int,intervalle.split())),manteau) for manteau,intervalle in zip(range(nbManteaux),stdin)] manteaux = [(debut,-fin,manteau) for (debut,fin),manteau in manteaux]

On cree une liste de triplets (debut,-fin,manteau), où debut et fin sont les deux bornes de température, et "manteau" sert juste à numéroter les manteaux.

manteaux.sort()

On les trie par "début" croissant. Note qu'en cas d'égalité, le tri regarde ensuite la deuxième composante, et trie par "fin" décroissante.

   parDebut = [None]*nbManteaux
   for position,(_,_,manteau) in enumerate(manteaux):
      parDebut[manteau] = position

On associe à chaque manteau sa position dans le tableau trié par (début, -fin).
Si le manteau est en position k, ça veut dire que les k manteaux situés avant lui ne sont pas compris dans son intervalle (car leur début est plus petit).

   manteaux.sort(key=itemgetter(1,0,2))
   parFin = [None]*nbManteaux
   for position,(_,_,manteau) in enumerate(manteaux):
      parFin[manteau] = position

Cette fois on trie en fonction du couple (-fin, debut), par ordre lexicographique. Du coup on les trie par "fin" décroissante, et en cas d'égalité, par début croissant.
Là encore la position indique combien de manteaux le sont pas compris dans son intervalle (car leur fin est plus grande)

   INFINI = 1000*1000*1000
   sommePosMin = INFINI
   for posDebut,posFin in zip(parDebut,parFin):
      sommePosMin = min(sommePosMin,posDebut+posFin)
   print(nbManteaux-1-sommePosMin)
 

Pour chaque manteau on fait la somme des deux positions et ça nous dit combien de manteaux ne sont pas dans son intervalle. On cherche donc le manteau pour lequel la somme des deux positions est minimale.

Le seul hic c'est qu'on risque de compter un manteau en double: s'il était situé avant dans le premier tri et dans le deuxieme tri. Mais ça veut dire que son début est plus petit, et que sa fin est plus grande, on est contenu dans son intervalle et il aura une SommePos encore plus petite.

Super, merci pour l'explication