Emprunter la file de réservation : des réservations équitables
Pourquoi c'est important Les systèmes de réservation construits à partir de zéro ont tendance à récompenser celui qui clique le plus vite, ou à laisser une personne absente bloquer tout le monde. Les endroits qui distribuent tous les jours des choses rares à des gens ont adopté une meilleure conception depuis longtemps.
Trois comptoirs
Une réservation à la bibliothèque. Tu réserves un livre qui est sorti. Quand un exemplaire revient, il va à la première personne de la file de réservation, qui reçoit un message et quelques jours pour venir le chercher. Si elle ne vient pas, l'exemplaire va à la personne suivante, et la première perd sa place.
Une liste d'attente de restaurant avec un bipeur. Tu donnes ton nom et tu reçois un bipeur. Quand une table se libère, le groupe suivant est bipé et a cinq minutes pour rejoindre l'accueil, sinon la table va au groupe suivant.
Le ticket du comptoir charcuterie. Tu prends un numéro. Quand ton numéro est appelé et que tu n'es pas là, le numéro suivant est appelé. Tu peux prendre un nouveau ticket, à la fin.
Compare avant de coder
- Dans chacun, quand ta place dans la file est-elle fixée : quand tu demandes, ou quand la chose devient libre ?
- Que se passe-t-il pour une personne qui ne vient pas, et de combien de temps dispose-t-elle ?
- Que devient la chose pendant qu'elle attend que quelqu'un vienne la chercher ?
- Énonce la règle commune en une phrase qui ne mentionne ni livres, ni tables, ni charcuterie.
La cible
L'équipe mobile partage un petit labo de téléphones de test. Les ingénieurs demandent un modèle ; quand un téléphone de ce modèle est libre, il leur est proposé, et ils doivent le réclamer dans l'appli du labo dans les deux heures. Un téléphone réclamé est réservé pour un créneau de huit heures puis revient automatiquement. Aujourd'hui l'appli donne un téléphone libre à celui qui appuie le premier sur « réclamer », et des gens ont commencé à écrire des scripts pour appuyer.
stock = [("dev1", "pixel")]
events = [("request", 0, "ana", "pixel"), ("request", 5, "ben", "pixel"),
("claim", 10, "ben", "pixel"), ("claim", 30, "ana", "pixel")]
loans(stock, events) # -> [("ana", "dev1", 30)] (ben is not first)Écris loans(stock, events). stock liste des (device_id, model), tous libres au temps 0. events sont des ("request", t, person, model) ou ("claim", t, person, model), triés par temps t en minutes. Les règles :
- Chaque modèle a une file dans l'ordre des demandes. Une demande est ignorée si cette personne est déjà dans la file de ce modèle, ou a déjà une offre en cours dessus.
- Un téléphone libre est proposé à la première personne de la file de son modèle (elle quitte la file). Si personne n'attend, il attend sur l'étagère, et une demande ultérieure pour ce modèle l'obtient tout de suite. S'il y en a plusieurs sur l'étagère, propose le plus petit id d'appareil.
- Une offre faite au temps
opeut être réclamée tant quet < o + 120. Une réclamation sans offre en cours pour cette personne et ce modèle est ignorée. - À
o + 120, une offre non réclamée expire et le téléphone est libéré à nouveau à ce moment (règle 2). - Une réclamation au temps
tdémarre un prêt ; le téléphone est libéré àt + 480. - Les expirations et les retours dus au plus tard au moment d'un événement ont lieu avant lui, dans l'ordre du temps, puis de l'id d'appareil.
(person, device_id, claim_time) dans l'ordre où ils ont été réclamés.
Tu as repéré un problème dans cette leçon ? Signale-le · Pose une question sur cette leçon
Cet exercice s'ouvre bientôt
Termine la leçon précédente pour débloquer celle-ci. Tout le cours est gratuit, aucun compte n'est requis, et tu peux lire cette leçon dès maintenant.
Ce navigateur bloque les cookies pour learn.floati.life, donc les leçons que tu as terminées ici ne peuvent pas s'ouvrir dans l'ordre. Autorise les cookies pour ce site et recharge la page.