Résoudre des problèmes algorithmiques: la possibilité de réserver un hôtel

La traduction de l'article a été préparée spécialement pour les étudiants du cours "Algorithmes pour les développeurs" .



Cet article fait partie d'une série sur la façon de résoudre des problèmes algorithmiques. Sur la base de mon expérience personnelle, j'ai constaté que la plupart des ressources décrivent simplement la solution en détail. Une explication du principal raisonnement qui permet de trouver une solution efficace, malheureusement, n'est pas très courante. Par conséquent, l'objectif de cette série est de décrire le cours possible du raisonnement pour résoudre les problèmes à partir de zéro.

---

Défi

• Tâche: InterviewBit

Le directeur de l'hôtel doit traiter N commandes de réservation pour la prochaine saison. Son hôtel dispose de K chambres. Les informations de réservation contiennent la date d'arrivée et la date de départ. Le directeur veut savoir s'il y a suffisamment de chambres dans l'hôtel pour satisfaire la demande.

Données d'entrée:

- Le premier à entrer une liste avec des informations sur l'heure d'arrivée
- Deuxième - une liste avec des informations sur l'heure de départ
- Troisième - K, indiquant le nombre de chambres

Données de sortie:
- Une valeur logique qui indique la possibilité de réserver des chambres
false signifie que l'hôtel ne dispose pas de suffisamment de chambres pour N réservations
true signifie que l'hôtel dispose de suffisamment de chambres pour N réservations

Un exemple:

Données d'entrée:
- enregistrement = [1, 3, 5]
- départ = [2, 6, 10]
- K = 1

Sortie: fausse. Le jour = 5, l'hôtel a 2 personnes. Mais nous n'avons qu'un seul numéro.

• Catégorie: Tableaux

Processus décisionnel

Cette tâche est intéressante, à mon avis, car il existe de nombreuses façons de la résoudre. Examinons les options.

Une structure qui stocke des compteurs pour chaque jour
La première idée peut être que nous avons besoin d'une structure pour stocker le nombre de commandes pour chaque jour. Cette structure peut être un tableau de taille fixe (déterminé par le jour de départ maximum).

Données d'entrée:
- entrées = [1, 3, 5]
- départs = [2, 6, 10]
- k = 1

Pour cet exemple, la taille du tableau sera 10 (car la dernière sortie le jour 10). Pour remplir ce tableau, nous parcourons les listes d'entrées et de sorties et augmentons ou diminuons le compteur du jour correspondant. Exemple de pseudo-code:

int[] counts = new int[maxDepartures(departures)] for each arr in arrivals { counts[arr]++ } for each dep in departures { counts[dep]-- } 

En conséquence, nous obtenons le tableau suivant:

: 1 0 1 1 2 1 1 1 1 0
: 1 2 3 4 5 6 7 8 9 10

Une fois que le tableau est plein, il vous suffit de le parcourir et de vérifier si tous les éléments ne dépassent pas k (nombre de pièces).

Dans l'exemple précédent, le nombre maximum de chambres était de 1. Puisque le jour 5 nous avons 2 réservations, nous retournons false .

La complexité temporelle de cette solution est O (n), où n est le nombre de réservations, et spatiale est O (m), où m est le jour de départ maximum. Pas mal en théorie, mais il est susceptible d'allouer beaucoup de mémoire pour un grand tableau, bien que la majeure partie ne soit pas utilisée.

Par exemple:

Données d'entrée:
- entrées = [1, 3, 5]
- départs = [2, 10000, 10]
- k = 1

Dans ce cas, un tableau de 10 000 entiers sera alloué.

Regardons d'autres solutions.

Stockage de la collection d'événements

Quelles sont les autres options? Regardons à nouveau ce qui s'est passé avec la structure précédente:

: 1 0 1 1 2 1 1 1 1 0
: 1 2 3 4 5 6 7 8 9 10

Nous constatons que certaines informations sont dupliquées. Par exemple, entre 6 et 9 jours, le nombre de réservations ne change pas, car nous savons que rien ne se passera pendant cette période.

Serait-il préférable que les événements soient stockés à la place? Reprenons le même exemple:

Données d'entrée:
- entrées = [1, 3, 5]
- départs = [2, 6, 10]
Jour 1: +1 réservation
Jour 2: -1 réservation
Jour 3: +1 réservation
Jour 6: -1 réservation
Jour 5: +1 réservation
Jour 10: -1 réservation

La solution est d'itérer sur ces événements pour augmenter ou diminuer le compteur. Si à un moment donné le compteur est supérieur à k , nous retournons false . Cependant, pour effectuer une recherche, cette collection d'événements doit être triée.

Quelle structure est préférable d'utiliser ici? Résumons nos exigences:

• Rechercher pour vérifier si une telle journée existe déjà
• Ajout d'un nouveau jour,
• Affichez la structure pour itérer sur chaque jour trié.

Que diriez-vous d'utiliser un arbre de recherche binaire (BST)?

Chaque nœud peut être représenté comme suit:

 class Node { int day int count Node left Node right } 

Le tri se fera sur le champ day .

Regardons les conséquences en termes de complexité temporelle:

• Rechercher pour vérifier si un tel jour existe déjà: O (log (n)) dans le cas moyen, O (n) dans le pire des cas,
• Ajout d'un nouveau jour: O (log (n)) dans le cas moyen, O (n) dans le pire des cas,
• Affichez la structure d'itération pour chaque jour trié: O (n) à l'aide d'une recherche en profondeur.

Comme nous devons parcourir chaque élément et l'insérer dans l'arbre, la complexité de l'algorithme est O (n log (n)) dans le cas moyen, O (n²) dans le pire des cas.

Une autre option consiste à utiliser une table de hachage et à trier les clés après avoir ajouté tous les événements:

• Rechercher pour vérifier si un tel jour existe déjà: O (1) dans le cas moyen, O (n) dans le pire des cas (la probabilité dépend de la capacité du tableau associatif),
• Ajout d'un nouveau jour: O (1) dans le cas moyen, O (n) dans le pire des cas,
• Affichez la structure d'itération sur chaque jour trié: O (n log (n)) pour les clés de tri et O (n) pour le tri.

Au final, la solution a O (n log (n)) dans le cas du milieu (en raison de l'opération de tri), O (n²) dans le pire des cas. Cette solution semble avoir la même complexité qu'une solution arborescente.

Examinons une implémentation possible en Java à l'aide d'un tableau associatif trié:

 public boolean hotel(ArrayList<Integer> arrivals, ArrayList<Integer> departures, int k) { //   Map<Integer, Integer> events = new HashMap<>(); //   int n = arrivals.size(); for (int i = 0; i < n; i++) { int arrival = arrivals.get(i); int departure = departures.get(i); //      Integer current = events.get(arrival); events.put(arrival, current == null ? 1 : current + 1); //      current = events.get(departure); events.put(departure, current == null ? -1 : current - 1); } //    Map<Integer, Integer> sortedEvents = new TreeMap<>(events); int count = 0; for (Map.Entry<Integer, Integer> entry : sortedEvents.entrySet()) { count += entry.getValue(); //  count     if (count > k) { return false; } } return true; } 

Complexité spatiale constante

Si nous voulons optimiser notre algorithme, nous devons nous demander s'il est vraiment nécessaire de stocker tous ces événements? Ne pouvons-nous pas simplement trier les données de collecte (entrées et sorties) et vérifier la limite de réservation dans le processus?

Une solution est possible, mais pour cela il faudrait simplifier les données d'entrée en les triant à l'avance.

Si les deux collections sont triées, nous pouvons simplement parcourir chaque élément à l'aide de deux pointeurs (un pour les entrées et un pour les départs), et effectuer une vérification des restrictions à la volée.

Comme vous pouvez le voir, à chaque itération, nous devons encore vérifier le minimum entre arrivals.get(indexArrival) departures.get(indexDeparture) pour savoir quel pointeur doit être mis à jour.

En général, l'algorithme a une complexité temporelle et spatiale constante O (n log (n)) due aux opérations de tri.