예약 대기열을 빌려 오기: 공정한 예약
왜 중요한가 처음부터 만든 예약 시스템은 가장 빨리 누르는 사람에게 보상하거나, 나타나지 않는 사람 하나가 모두를 막게 두는 경향이 있어요. 귀한 것을 매일 사람들에게 나눠 주는 곳들은 오래전에 더 나은 설계에 자리 잡았어요.
창구 셋
도서관 예약. 대출 중인 책에 예약을 걸어요. 한 권이 돌아오면 예약 대기열의 첫 사람에게 가고, 그 사람은 메시지와 찾아갈 며칠을 받아요. 오지 않으면 책은 다음 사람에게 가고, 첫 사람은 자리를 잃어요.
진동벨이 있는 식당 대기 명단. 이름을 대고 진동벨을 받아요. 테이블이 비면 다음 일행의 벨이 울리고 5분 안에 안내대에 닿아야 해요. 아니면 테이블은 다음 일행에게 가요.
델리 계산대 번호표. 번호를 뽑아요. 번호가 불렸는데 없으면 다음 번호가 불려요. 맨 뒤의 새 번호표를 뽑을 수 있어요.
코딩 전에 비교하기
- 각각에서 줄의 자리는 언제 정해지나: 요청할 때, 아니면 그것이 빌 때?
- 나타나지 않는 사람은 어떻게 되고, 얼마나 시간을 받나?
- 누군가 찾아가기를 기다리는 동안 그것은 어떻게 되나?
- 책, 테이블, 고기를 언급하지 않는 한 문장으로 공유된 규칙을 말하세요.
목표
모바일 팀이 테스트 휴대폰의 작은 실험실을 공유해요. 엔지니어가 모델을 요청하고, 그 모델의 휴대폰이 비면 제안되고, 실험실 앱에서 두 시간 안에 찾아가야 해요. 찾아간 휴대폰은 여덟 시간 칸으로 예약되고 그다음 자동으로 돌아와요. 오늘 앱은 빈 휴대폰을 "찾아가기"를 먼저 누르는 사람에게 주고, 사람들이 그걸 누르는 스크립트를 쓰기 시작했어요.
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)loans(stock, events)를 쓰세요. stock은 (device_id, model)을 나열하고, 모두 시간 0에 비어 있어요. events는 시간 t(분)순으로 정렬된 ("request", t, person, model)이나 ("claim", t, person, model)이에요. 규칙:
- 각 모델에는 요청 순서의 큐가 있어요. 그 사람이 이미 그 모델의 큐에 있거나 제안을 쥐고 있으면 요청은 무시돼요.
- 빈 휴대폰은 그 모델 큐의 첫 사람에게 제안돼요(그 사람은 큐를 떠나요). 아무도 큐에 없으면 선반에서 기다리고, 그 모델의 뒤 요청이 바로 그걸 받아요. 선반에 여럿 있으면 가장 작은 기기 id를 제안하세요.
- 시간
o에 한 제안은t < o + 120인 동안 찾아갈 수 있어요. 그 사람과 모델에 살아 있는 제안이 없는 찾아가기는 무시돼요. o + 120에 찾아가지 않은 제안은 만료되고 휴대폰은 그 순간 다시 비어요(규칙 2).- 시간
t의 찾아가기는 대여를 시작하고, 휴대폰은t + 480에 비어요. - 이벤트 시간 이하에 예정된 만료와 반납은 그것 전에, 시간순, 그다음 기기 id순으로 일어나요.
(person, device_id, claim_time)으로 반환하세요.
이 연습은 곧 열려요
앞의 레슨을 마치면 이 레슨이 열려요. 강좌 전체가 무료이고 계정도 필요 없으며, 이 레슨은 지금 바로 읽을 수 있어요.
이 브라우저가 learn.floati.life의 쿠키를 막고 있어서, 여기서 마친 레슨들이 순서대로 열리지 않아요. 이 사이트의 쿠키를 허용하고 새로고침하세요.