Challenge 3 - Prochaine fin du monde

Il existe beaucoup de prophéties de la forme : « La fin du monde aura lieu entre telle année et telle année ». Ainsi, si une prophétie prédit la fin du monde entre l'année 2090 et l'année 2093, la fin du monde pourrait avoir lieu en 2090, 2091, 2092, ou 2093 (4 possibilités).

Étant donné un ensemble de prophéties de cette forme, vous vous posez la question suivante : « si l'on suppose que toutes les prophéties sont vraies, combien y a-t-il d'années distinctes auxquelles la fin du monde pourrait se produire ? ». Écrivez un programme qui répond à cette question. Notez que la réponse peut éventuellement être zéro.

Limites de temps et de mémoire (Python)

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

Contraintes

  • 1 <= nbPropheties <= 10 000, où nbPropheties est le nombre de prophéties
  • 0 <= anneeMini <= anneeMaxi <= 10 000, où anneeMini et anneeMaxi sont respectivement l'année minimale et l'année maximale de la fin du monde, d'après la prophétie i.

Entrée

La première ligne de l'entrée contient un entier : nbPropheties.

Chacune des nbPropheties lignes suivantes décrit une prophétie par deux entiers séparés par un espace, anneeMini et anneeMaxi.

Sortie

Vous devez afficher le nombre d'années durant lesquelles la fin du monde peut avoir lieu en respectant toutes les prophéties à la fois.

Pour avoir les 100 points, votre programme doit être aussi efficace que possible.

Exemples

Exemple 1

entrée : 

5
7 19
9 25
3 21
11 22
2 17

sortie : 

7

Exemple 2

entrée : 

6
3 17
9 30
14 19
9 20
1 13
11 22

sortie : 

0

Commentaires

Dans le premier exemple les années 11, 12, 13, 14, 15, 16 et 17 font partie de toutes les prophéties, il y a donc 7 années possibles.

Dans le second exemple les prophéties 3 (années 14 à 19) et 5 (années 1 à 13) n'ont aucune année en commun, il y a donc 0 année possible.

Pensez à faire des dessins pour vous représenter le problème.

EXEMPLE DE CODE

Pour vous aider avec la lecture des données d'entrée, vous pouvez prendre comme modèle l'exemple de programme ci-dessous, qui lit la description des prophéties, puis affiche l'entier 42. 

#include <stdio.h>
 
int main()
{
   int nbIntervalles;
   scanf("%d", &nbIntervalles);
   for (int iIntervalle = 0; iIntervalle < nbIntervalles; iIntervalle = iIntervalle + 1)
   {
      int debut, fin;
      scanf("%d %d", &debut, &fin);
   }

   printf("%d\n",42);
   return 0;
}

#include <iostream>
using namespace std;
 
int main()
{
   int nbIntervalles;
   cin >> nbIntervalles;
   for (int iIntervalle = 0; iIntervalle < nbIntervalles; iIntervalle = iIntervalle + 1)
   {
      int debut, fin;
      cin >> debut >> fin;
   }

   cout << 42 << endl;
   return 0;
}

import algorea.Scanner;

class Main
{
   public static void main(String [] args)
   {
      Scanner input = new Scanner(System.in);
      int nbIntervalles = input.nextInt();
      for (int iIntervalle = 0; iIntervalle < nbIntervalles; iIntervalle = iIntervalle + 1)
      {
         int debut = input.nextInt();
         int fin = input.nextInt();
      }
      System.out.println(42);
   }
}

Notez bien l'utilisation de algorea.Scanner, le Scanner de Java étant trop lent et gourmand en mémoire, il est très fortement déconseillé de l'utiliser. 

void main()
{
   int nbIntervalles = readInt();
   for (int iIntervalle = 0; iIntervalle < nbIntervalles; iIntervalle = iIntervalle + 1)
   {
      int debut = readInt();
      int fin = readInt();
   }
   println(42);
}

let read_int() = Scanf.scanf " %d" (fun x -> x)
let nbIntervalles = read_int()
let _ =
   for iIntervalle = 1 to nbIntervalles do
      let debut = read_int() in
      let fin   = read_int() in
      ()
   done;
   print_int 42;
   print_newline()

program Solution;
var
   iIntervalle, nbIntervalles, debut, fin: LongInt;
begin
   readln(nbIntervalles);
   for iIntervalle := 1 to nbIntervalles do
   begin
      readln(debut, fin);
   end;
   writeln(42)
end.

nbIntervalles = int(input())
for loop in range(nbIntervalles):
   debut, fin = map(int, input().split())

print(42)
Source : https://www.france-ioi.org/