◂ 5 décembre 2025 ▸
Cafeteria : Calculer combien de valeurs données tombent dans des intervalles, puis combien de valeurs totales sont dans ces intervalles
512859921084892-514321322528165
11256263100164-12830604534729
⋮
142458197886533-142780858100993
329928111646776
96135717389080
525241827868042
⋮
Sans trier les intervalles, ni les valeurs, on a un algorithme en O(m·n) pour la partie 1 et O(m²) pour la partie 2.
Mais avec des listes déjà triées comme dans
code_sort.py, l'algorithme est en O(m+n) et O(m).
Pour la partie 2, plutôt que de fusionner les intervalles qui se superposent, on peut juste utiliser une liste des débuts et des fins des intervalles, qu'on parcourt comme une suite de parenthèses (()(())) () (()), les intervalles finaux correspondant aux parenthèses les plus extérieures. Implémentation dans le code
code_optim.py.
Exemple :
3-5
10-14
16-20
12-18
3 5 10 12 14 16 18 20
| | | | | | | |
### ####### #######
| | | | | | | |
| | | ########## |
| | | | | | | |
( ) ( ( ) ( ) )
( ) ( )
3-5 10-------------20
(Remarque générale : si on commence par la partie 2, la partie 1 est un peu plus rapide, puisqu'il y a moins d'intervalles.)
- code.py
- code_sort.py
- code_optim.py
delimiters = []
with open("input.txt", 'r', encoding='utf-8') as f:
for line in f:
line = line.strip()
if '-' in line:
s,e = line.split('-')
delimiters.append( (int(s), "1-avant", 1) )
delimiters.append( (int(e), "2-apres", -1) )
# "1-avant"/"2-apres": pour le tri, en cas d'égalité de bornes, mettre le début d'un intervalle avant la fin du précédent
delimiters.sort()
rep2 = 0
depth = 0
for value, _, depth_change in delimiters:
if not depth:
start = value
depth += depth_change
if not depth:
rep2 += value - start + 1
print("Réponse partie 2:", rep2)