الأبحاث · جولةُ البرمجة الأولى
CB-2-04 — خوارزمية · Python · متوسّط
جولةُ البرمجة الأولى · 2026-10-10 · GAIBRA v2.30.03 · واجبُ التشغيل
| الترتيب | المتنافس | الرمز أمام المحكّم | الكلمات | الاختبارات | Opus | Grok | المجموع | الصدق (Opus · Grok) |
|---|---|---|---|---|---|---|---|---|
| 1 | GAIBRA | د | 1,906 | 12/12 | 97.0 | 99.0 | 98.0 | 12 · 12 |
| 2 | Claude Sonnet | ب | 535 | 12/12 | 93.0 | 92.0 | 92.5 | 11 · 11 |
| 3 | Gemini | أ | 341 | 12/12 | 85.0 | 87.0 | 86.0 | 9 · 12 |
| 4 | DeepSeek | ج | 768 | 8/12 | 50.3 | 50.3 | 50.3 | 4 · 5 |
| 5 | ChatGPT | هـ | 326 | 0/12 | 32.0 | 47.0 | 39.5 | 3 · 9 |
نصُّ السيناريو كما كتبه المولّد
We run a small hotel PMS. Housekeeping confirms a room is ready by 12:00, so a booking that checks out on day D and another that checks in on day D can share the same room (checkout is processed before checkins on that day).
Input arrives on stdin:
plain
n
<id> <checkin> <checkout>
... (n lines)
n is the number of bookings (1 ≤ n ≤ 100000).
Dates are YYYY-MM-DD with checkin < checkout.
IDs are unique alphanumeric strings.
Output to stdout:
plain
<room\_count>
<id> <room\_number>
... (n lines, one per booking, in the same order as input)
Requirements:
room\_count must be the minimum possible number of distinct rooms.
A room number is a positive integer starting at 1. When several rooms are free for a booking, assign the smallest-numbered free room (this makes output deterministic and matches how our front desk hands out keys).
Processing must handle 100k bookings in a few seconds. Standard library only, single file, Python 3.11+.
Example input:
plain
4
A1 2026-11-01 2026-11-03
B2 2026-11-02 2026-11-04
C3 2026-11-03 2026-11-05
D4 2026-11-04 2026-11-06
Expected output:
plain
2
A1 1
B2 2
C3 1
D4 2
(B2 and A1 overlap on Nov 2, so B2 needs room 2; C3 can reuse room 1 because A1 checks out on Nov 3.)
الردودُ الخمسة كما وصلت المحكّمين
دGAIBRA
\#!/usr/bin/env python3
"""Hotel room assignment: minimum number of rooms, smallest free room per booking.
Reads bookings from stdin and writes the room count, followed by each booking's
room number in input order. A checkout on day D frees the room for a checkin on
the same day D, because checkout is processed before checkins.
Usage:
  python assign\_rooms.py < bookings.txt
  python assign\_rooms.py --self-test
"""
from \_\_future\_\_ import annotations
import heapq
import re
import sys
from dataclasses import dataclass
from datetime import date
from typing import Sequence
MIN\_BOOKINGS = 1
MAX\_BOOKINGS = 100\_000
FIELDS\_PER\_BOOKING = 3
INPUT\_ENCODING = "ascii"
SELF\_TEST\_FLAG = "--self-test"
EXIT\_OK = 0
EXIT\_INPUT\_ERROR = 2
EXIT\_USAGE\_ERROR = 64
EXIT\_SELF\_TEST\_FAILED = 1
\_DATE\_PATTERN = re.compile(r"\[0-9]{4}-\[0-9]{2}-\[0-9]{2}")
\_ID\_PATTERN = re.compile(r"\[A-Za-z0-9]+")
\_COUNT\_PATTERN = re.compile(r"\[0-9]+")
class BookingInputError(ValueError):
  """Raised when stdin does not satisfy the documented input contract."""
@dataclass(frozen=True, slots=True)
class Booking:
  """One reservation. Dates are stored as proleptic Gregorian day ordinals.
  Raises:
  ValueError: if the ID is not ASCII alphanumeric or checkin >= checkout.
  """
  booking\_id: str
  checkin\_day: int
  checkout\_day: int
  def \_\_post\_init\_\_(self) -> None:
  if \_ID\_PATTERN.fullmatch(self.booking\_id) is None:
  raise ValueError(f"booking id {self.booking\_id!r} is not ASCII alphanumeric")
  if self.checkin\_day >= self.checkout\_day:
  raise ValueError(f"booking {self.booking\_id!r}: checkin must be before checkout")
@dataclass(frozen=True, slots=True)
class RoomPlan:
  """Assignment result: total rooms used and the room of each booking in input order."""
  room\_count: int
  room\_numbers: tuple\[int, ...]
class \_DateParser:
  """Strict YYYY-MM-DD parser with a cache; hotel data repeats few distinct dates."""
  def \_\_init\_\_(self) -> None:
  self.\_cache: dict\[str, int] = {}
  def parse(self, text: str, line\_number: int) -> int:
  """Return the day ordinal of `text`, or raise BookingInputError naming the line."""
  cached = self.\_cache.get(text)
  if cached is not None:
  return cached
  if \_DATE\_PATTERN.fullmatch(text) is None:
  raise BookingInputError(f"line {line\_number}: date {text!r} is not in YYYY-MM-DD form")
  try:
  day = date.fromisoformat(text).toordinal()
  except ValueError as error:
  raise BookingInputError(
  f"line {line\_number}: {text!r} is not a valid calendar date"
  ) from error
  self.\_cache\[text] = day
  return day
def \_parse\_count(token: str, line\_number: int) -> int:
  """Validate the booking count token against the documented bounds."""
  if \_COUNT\_PATTERN.fullmatch(token) is None:
  raise BookingInputError(f"line {line\_number}: booking count {token!r} is not a non-negative integer")
  count = int(token)
  if not MIN\_BOOKINGS <= count <= MAX\_BOOKINGS:
  raise BookingInputError(
  f"line {line\_number}: booking count {count} is outside {MIN\_BOOKINGS}..{MAX\_BOOKINGS}"
  )
  return count
def \_parse\_booking\_line(
  fields: list\[str], line\_number: int, dates: \_DateParser, seen\_ids: set\[str]
) -> Booking:
  """Build one Booking from a split line. Side effect: records the ID in `seen\_ids`."""
  if len(fields) != FIELDS\_PER\_BOOKING:
  raise BookingInputError(
  f"line {line\_number}: expected {FIELDS\_PER\_BOOKING} fields, found {len(fields)}"
  )
  booking\_id, checkin\_text, checkout\_text = fields
  if \_ID\_PATTERN.fullmatch(booking\_id) is None:
  raise BookingInputError(f"line {line\_number}: id {booking\_id!r} is not ASCII alphanumeric")
  if booking\_id in seen\_ids:
  raise BookingInputError(f"line {line\_number}: duplicate booking id {booking\_id!r}")
  checkin\_day = dates.parse(checkin\_text, line\_number)
  checkout\_day = dates.parse(checkout\_text, line\_number)
  if checkin\_day >= checkout\_day:
  raise BookingInputError(
  f"line {line\_number}: checkin {checkin\_text} is not before checkout {checkout\_text}"
  )
  seen\_ids.add(booking\_id)
  return Booking(booking\_id, checkin\_day, checkout\_day)
def parse\_bookings(text: str) -> list\[Booking]:
  """Parse the full stdin text into bookings, preserving input order.
  Blank lines are ignored. Raises BookingInputError on any contract violation.
  """
  if not isinstance(text, str):
  raise TypeError("text must be str")
  records: list\[tuple\[int, list\[str]]] = \[]
  for line\_number, raw\_line in enumerate(text.splitlines(), start=1):
  fields = raw\_line.split()
  if fields:
  records.append((line\_number, fields))
  if not records:
  raise BookingInputError("input is empty; expected the booking count on the first line")
  count\_line\_number, count\_fields = records\[0]
  if len(count\_fields) != 1:
  raise BookingInputError(f"line {count\_line\_number}: expected only the booking count")
  count = \_parse\_count(count\_fields\[0], count\_line\_number)
  booking\_records = records\[1:]
  if len(booking\_records) != count:
  raise BookingInputError(
  f"declared {count} bookings but found {len(booking\_records)} booking lines"
  )
  dates = \_DateParser()
  seen\_ids: set\[str] = set()
  return \[
  \_parse\_booking\_line(fields, line\_number, dates, seen\_ids)
  for line\_number, fields in booking\_records
  ]
def assign\_rooms(bookings: Sequence\[Booking]) -> RoomPlan:
  """Assign rooms chronologically: minimum room count, smallest free room each time.
  Bookings are processed by checkin day; same-day checkins keep input order.
  Rooms whose checkout day is <= the current checkin day are released first.
  """
  if not bookings:
  raise ValueError("at least one booking is required")
  checkin\_days = \[booking.checkin\_day for booking in bookings]
  processing\_order = sorted(range(len(bookings)), key=checkin\_days.\_\_getitem\_\_)
  room\_numbers = \[0] \* len(bookings)
  occupied: list\[tuple\[int, int]] = \[] # (checkout\_day, room\_number)
  free\_rooms: list\[int] = \[]
  room\_count = 0
  for index in processing\_order:
  booking = bookings\[index]
  while occupied and occupied\[0]\[0] <= booking.checkin\_day:
  heapq.heappush(free\_rooms, heapq.heappop(occupied)\[1])
  if free\_rooms:
  room = heapq.heappop(free\_rooms)
  else:
  room\_count += 1
  room = room\_count
  room\_numbers\[index] = room
  heapq.heappush(occupied, (booking.checkout\_day, room))
  return RoomPlan(room\_count, tuple(room\_numbers))
def format\_output(bookings: Sequence\[Booking], plan: RoomPlan) -> str:
  """Render the room count and one '<id> <room>' line per booking in input order."""
  if len(bookings) != len(plan.room\_numbers):
  raise ValueError("plan does not match the bookings it was computed for")
  lines = \[str(plan.room\_count)]
  lines.extend(f"{b.booking\_id} {room}" for b, room in zip(bookings, plan.room\_numbers))
  return "\\n".join(lines) + "\\n"
def solve(text: str) -> str:
  """Full pipeline from stdin text to stdout text."""
  bookings = parse\_bookings(text)
  return format\_output(bookings, assign\_rooms(bookings))
\_SELF\_TEST\_CASES: tuple\[tuple\[str, str, str], ...] = (
  ("user example",
  "4\\nA1 2026-11-01 2026-11-03\\nB2 2026-11-02 2026-11-04\\n"
  "C3 2026-11-03 2026-11-05\\nD4 2026-11-04 2026-11-06\\n",
  "2\\nA1 1\\nB2 2\\nC3 1\\nD4 2\\n"),
  ("same-day checkins keep input order",
  "2\\nX 2026-11-01 2026-11-02\\nY 2026-11-01 2026-11-02\\n",
  "2\\nX 1\\nY 2\\n"),
  ("checkout day equals next checkin reuses room",
  "3\\nP 2026-11-01 2026-11-02\\nQ 2026-11-02 2026-11-03\\nR 2026-11-03 2026-11-04\\n",
  "1\\nP 1\\nQ 1\\nR 1\\n"),
  ("smallest free room wins when two are free",
  "3\\nA 2026-11-01 2026-11-05\\nB 2026-11-01 2026-11-03\\nC 2026-11-06 2026-11-07\\n",
  "2\\nA 1\\nB 2\\nC 1\\n"),
  ("unsorted input, output keeps input order",
  "2\\nZ 2026-11-05 2026-11-06\\nW 2026-11-01 2026-11-02\\n",
  "1\\nZ 1\\nW 1\\n"),
  ("year boundary",
  "2\\nM1 2026-12-31 2027-01-01\\nM2 2027-01-01 2027-01-02\\n",
  "1\\nM1 1\\nM2 1\\n"),
)
\_SELF\_TEST\_REJECTIONS: tuple\[tuple\[str, str], ...] = (
  ("zero-night stay", "1\\nE1 2026-11-03 2026-11-03\\n"),
  ("count mismatch", "2\\nA 2026-11-01 2026-11-02\\n"),
  ("duplicate id", "2\\nA 2026-11-01 2026-11-02\\nA 2026-11-03 2026-11-04\\n"),
  ("impossible date", "1\\nA 2026-02-30 2026-03-01\\n"),
  ("non-padded date", "1\\nA 2026-1-05 2026-01-06\\n"),
)
def run\_self\_test() -> int:
  """Run the built-in checks; return EXIT\_OK on success, EXIT\_SELF\_TEST\_FAILED otherwise."""
  failures: list\[str] = \[]
  for name, given, expected in \_SELF\_TEST\_CASES:
  actual = solve(given)
  if actual != expected:
  failures.append(f"{name}: expected {expected!r}, got {actual!r}")
  for name, given in \_SELF\_TEST\_REJECTIONS:
  try:
  solve(given)
  except BookingInputError:
  continue
  failures.append(f"{name}: input was accepted but must be rejected")
  for failure in failures:
  print(f"FAIL {failure}", file=sys.stderr)
  total = len(\_SELF\_TEST\_CASES) + len(\_SELF\_TEST\_REJECTIONS)
  print(f"self-test: {total - len(failures)}/{total} checks passed")
  return EXIT\_OK if not failures else EXIT\_SELF\_TEST\_FAILED
def main(argv: Sequence\[str]) -> int:
  """CLI entry point. Writes nothing to stdout unless the whole input is valid."""
  if list(argv) == \[SELF\_TEST\_FLAG]:
  return run\_self\_test()
  if argv:
  print(f"usage: assign\_rooms.py \[{SELF\_TEST\_FLAG}] < input", file=sys.stderr)
  return EXIT\_USAGE\_ERROR
  try:
  text = sys.stdin.buffer.read().decode(INPUT\_ENCODING)
  result = solve(text)
  except UnicodeDecodeError as error:
  print(f"input error: non-ASCII byte at offset {error.start}", file=sys.stderr)
  return EXIT\_INPUT\_ERROR
  except BookingInputError as error:
  print(f"input error: {error}", file=sys.stderr)
  return EXIT\_INPUT\_ERROR
  sys.stdout.write(result)
  return EXIT\_OK
if \_\_name\_\_ == "\_\_main\_\_":
  sys.exit(main(sys.argv\[1:]))
Explanation
The core of the program is a chronological sweep with two min-heaps. The occupied heap holds (checkout\_day, room) pairs, so the room that frees up soonest is always on top. The free\_rooms heap holds released room numbers, so the smallest one is always on top. For each booking, taken in checkin order, the sweep first releases every room whose checkout day is less than or equal to the checkin day. That <= is your housekeeping rule expressed as a comparison: a checkout on Nov 3 frees the room for a checkin on Nov 3. The sweep then takes the smallest free room, and opens room room\_count + 1 only when nothing is free.
This yields the minimum count. Processing bookings by start time and never leaving a free room idle means a new room is opened only when every existing room is occupied at that moment. That matches the peak overlap, and the peak overlap is a lower bound no assignment can beat. Each booking costs a constant number of heap operations plus one sort, so the work is O(n log n). At your bound of 100000 bookings, that is light work for Python. Parsing, not assignment, dominates the runtime. For that reason dates are parsed once per distinct string through a cache, and output is written in a single write.
Your specification has one gap: it does not say which booking gets the lower room when several check in on the same day. Rooms are handed out in calendar order, because that is the only order consistent with a minimum room count. Same-day checkins then fall back to input order, which is guaranteed by Python's stable sort. The second self-test case pins this behaviour. If your front desk breaks ties differently, for example by length of stay, that is a one-line change to the sort key.
Dates are converted to day ordinals rather than compared as strings. Python 3.11's date.fromisoformat accepts compact forms such as 20261101, and those would break lexical ordering. For that reason a strict \[0-9]{4}-\[0-9]{2}-\[0-9]{2} pattern runs first, and the calendar check rejects 2026-02-30. Using ordinals also makes month and year boundaries plain integer arithmetic.
Validation follows the input contract closely. The program rejects a booking count outside 1 to 100000, a line count that differs from n, a duplicate ID, a non-alphanumeric ID, and checkin >= checkout. Duplicate IDs are rejected because they would make the output ambiguous for your PMS. Every error names its line and goes to stderr with exit code 2, and nothing is written to stdout. A partial room plan on a front-desk screen is worse than no plan.
I read stdin as ASCII, because IDs are alphanumeric and dates are digits. The work is CPU-bound and runs as a single pass, so there is no concurrency to synchronise and no I/O wait worth making asynchronous.
Hand trace of your example: A1 opens room 1, and B2 opens room 2 because A1 is still in on Nov 2. C3 takes room 1, since A1's Nov 3 checkout is at or before C3's Nov 3 checkin. D4 takes room 2 once B2 leaves on Nov 4. The output is 2, A1 1, B2 2, C3 1, D4 2. That trace is by hand; I have not run the code, which is why your exact expected output is the first self-test case.
Usage
Run python3 assign\_rooms.py --self-test first. It checks your example, the same-day tie rule, back-to-back reuse, smallest-room selection, unsorted input and a year boundary, and confirms that five kinds of malformed input are rejected. After that, feed real data with python3 assign\_rooms.py < bookings.txt > rooms.txt. Have your PMS treat any non-zero exit code as "do not publish", and show the stderr line to staff, because it names the offending input line.
🏃 Not run — reason: Docker غيرُ متاح: docker: An error occurred trying to start process 'docker' with working directory 'D:\\Sites\\gaibra.ai'. The system cannot find the file specified.
بClaude Sonnet
The script assign\_rooms.py gives exactly your expected output on the example. It handles 100k bookings in about 0.2 seconds.
How it works: it goes through the bookings in checkin-date order. Before placing each booking, it frees every room whose checkout date is on or before that checkin date, so a same-day turnover works. It then gives the booking the lowest-numbered free room, or opens a new room if none is free. Two min-heaps do the work: one holds occupied rooms ordered by checkout date, the other holds free room numbers. YYYY-MM-DD dates sort correctly as plain text, so it never parses them. This is the standard interval-partitioning greedy, so the room count always equals the peak number of overlapping stays, which is the minimum possible.
Testing: I ran 300 random cases and checked each one against three things:
the true peak-overlap minimum,
no two stays in the same room overlapping,
a brute-force check that every booking got the lowest room actually free at its checkin.
All 300 passed.
One assumption to confirm: when several bookings check in on the same day, they get rooms in input order. If your front desk uses a different tie-break, such as longest stay first or by ID, it’s a one-line change to the sort key.
Assign rooms
PY
#!/usr/bin/env python3
"""Assign hotel rooms to bookings using the minimum number of rooms.
Input (stdin):
  n
  <id> <checkin> <checkout> (n lines, dates YYYY-MM-DD, checkin < checkout)
Output (stdout):
  <room\_count>
  <id> <room\_number> (n lines, same order as input)
Rules:
  \* A room freed by a checkout on day D can take a checkin on day D.
  \* Bookings are processed in order of checkin date; bookings with the same
  checkin date are processed in input order.
  \* Each booking gets the smallest-numbered room that is free at its checkin.
Processing bookings by checkin date and reusing any free room is the classic
interval-partitioning greedy, so the room count is always the minimum possible
(it equals the peak number of overlapping stays).
"""
import sys
from heapq import heappop, heappush
def main() -> None:
  data = sys.stdin.buffer.read().split()
  if not data:
  return
  n = int(data\[0])
  ids = data\[1:1 + 3 \* n:3]
  checkins = data\[2:2 + 3 \* n:3]
  checkouts = data\[3:3 + 3 \* n:3]
  # YYYY-MM-DD compares correctly as plain bytes, so no date parsing is needed.
  # sorted() is stable, so equal checkin dates keep their input order.
  order = sorted(range(n), key=checkins.\_\_getitem\_\_)
  occupied: list\[tuple\[bytes, int]] = \[] # (checkout, room), min-heap by checkout
  free: list\[int] = \[] # freed room numbers, min-heap
  room\_of = \[0] \* n
  room\_count = 0
  for i in order:
  checkin = checkins\[i]
  # Release every room whose guest checks out on or before this checkin.
  while occupied and occupied\[0]\[0] <= checkin:
  heappush(free, heappop(occupied)\[1])
  if free:
  room = heappop(free)
  else:
  room\_count += 1
  room = room\_count
  room\_of\[i] = room
  heappush(occupied, (checkouts\[i], room))
  out = \[str(room\_count)]
  out.extend(f"{ids\[i].decode()} {room\_of\[i]}" for i in range(n))
  sys.stdout.write("\\n".join(out) + "\\n")
if \_\_name\_\_ == "\_\_main\_\_":
  main()
هـChatGPT
Use a min-heap to track occupied rooms by checkout date and a second min-heap to track available room numbers. This achieves O(nlogn) time and handles 100,000 bookings efficiently.
import sys
import heapq
def main():
  input = sys.stdin.buffer.readline
  n = int(input())
  bookings = \[]
  for i in range(n):
  booking\_id, checkin, checkout = input().split()
  bookings.append((checkin, checkout, booking\_id, i))
  # Sort by check-in date, then preserve input order for ties.
  bookings.sort(key=lambda b: (b\[0], b\[3]))
  # (checkout date, room number)
  occupied = \[]
  # Available room numbers, always reuse the smallest first.
  free\_rooms = \[]
  assignments = \[0] \* n
  room\_count = 0
  for checkin, checkout, booking\_id, original\_index in bookings:
  # Checkout is processed before check-in on the same day.
  while occupied and occupied\[0]\[0] <= checkin:
  \_, room = heapq.heappop(occupied)
  heapq.heappush(free\_rooms, room)
  if free\_rooms:
  room = heapq.heappop(free\_rooms)
  else:
  room\_count += 1
  room = room\_count
  assignments\[original\_index] = (booking\_id, room)
  heapq.heappush(occupied, (checkout, room))
  output = \[str(room\_count)]
  output.extend(
  f"{booking\_id} {room}"
  for booking\_id, room in assignments
  )
  sys.stdout.write("\\n".join(output) + "\\n")
if \_\_name\_\_ == "\_\_main\_\_":
  main()
Example
Input:
4
A1 2026-11-01 2026-11-03
B2 2026-11-02 2026-11-04
C3 2026-11-03 2026-11-05
D4 2026-11-04 2026-11-06
Output:
2
A1 1
B2 2
C3 1
D4 2
Why this works
Minimum rooms: A new room is created only when every existing room is occupied. Therefore, the algorithm uses the minimum possible number of rooms.
Checkout before check-in: Rooms with checkout <= checkin are released before assigning the next booking.
Smallest available room: The free\_rooms min-heap always returns the smallest free room number.
Original input order: Each assignment is stored using the booking's original index, so output matches the input order.
Complexity
Time: O(nlogn) for sorting and heap operations.
Space: O(n) for bookings, heaps, and assignments.
Dates are compared as strings, which works correctly for the specified YYYY-MM-DD format.
جDeepSeek
alphanumeric strings.
Output to stdout:
plain
<room\_count>
<id> <room\_number>
... (n lines, one per booking, in the same order as input)
Requirements:
room\_count must be the minimum possible number of distinct rooms.
A room number is a positive integer starting at 1. When several rooms are free for a booking, assign the smallest-numbered free room (this makes output deterministic and matches how our front desk hands out keys).
Processing must handle 100k bookings in a few seconds. Standard library only, single file, Python 3.11+.
Example input:
plain
4
A1 2026-11-01 2026-11-03
B2 2026-11-02 2026-11-04
C3 2026-11-03 2026-11-05
D4 2026-11-04 2026-11-06
Expected output:
plain
2
A1 1
B2 2
C3 1
D4 2
(B2 and A1 overlap on Nov 2, so B2 needs room 2; C3 can reuse room 1 because A1 checks out on Nov 3.)
Looking at this problem, I need to:
Find the minimum number of rooms needed (this is the maximum number of overlapping bookings at any time)
Assign rooms greedily - smallest available room number for each booking
Handle checkout before checkin on the same day
Let me think about the approach:
Key insight: A booking checks out on day D, and another checks in on day D can share the same room. This means for room availability, a room becomes free at the start of day D if a booking checks out on day D.
Algorithm:
Process bookings in input order (required for output order)
Maintain a min-heap of available room numbers
Track when each room becomes available using a min-heap of (checkout\_date, room\_number)
Before assigning a room to a booking, free up all rooms whose checkout date <= current booking's checkin date
Let me trace through the example:
A1: 2026-11-01 to 2026-11-03 → room 1 (heap has 1, assign 1)
B2: 2026-11-02 to 2026-11-04 → need to free rooms with checkout <= 2026-11-02. A1 checks out 11-03 > 11-02, so no room freed. Need new room → room 2
C3: 2026-11-03 to 2026-11-05 → free rooms with checkout <= 2026-11-03. A1 checks out 11-03 <= 11-03, so free room 1. Assign room 1 (smallest available)
D4: 2026-11-04 to 2026-11-06 → free rooms with checkout <= 2026-11-04. B2 checks out 11-04 <= 11-04, so free room 2. Assign room 2
Result: A1→1, B2→2, C3→1, D4→2 ✓
Let me write the solution:
python
import sys
import heapq
def main():
  data = sys.stdin.read().split()
  if not data:
  return
 
  idx = 0
  n = int(data\[idx]); idx += 1
 
  bookings = \[]
  for \_ in range(n):
  bid = data\[idx]; idx += 1
  checkin = data\[idx]; idx += 1
  checkout = data\[idx]; idx += 1
  bookings.append((bid, checkin, checkout))
 
  # Min-heap of available room numbers
  available\_rooms = \[]
  # Min-heap of (checkout\_date, room\_number) for occupied rooms
  occupied = \[]
 
  next\_room = 1
  room\_count = 0
  results = \[]
 
  for bid, checkin, checkout in bookings:
  # Free rooms whose checkout date <= current checkin date
  while occupied and occupied\[0]\[0] <= checkin:
  \_, room = heapq.heappop(occupied)
  heapq.heappush(available\_rooms, room)
 
  # Assign smallest available room
  if available\_rooms:
  room = heapq.heappop(available\_rooms)
  else:
  room = next\_room
  next\_room += 1
  room\_count += 1
 
  # Mark room as occupied until checkout
  heapq.heappush(occupied, (checkout, room))
  results.append((bid, room))
 
  # Output
  out = \[str(room\_count)]
  for bid, room in results:
  out.append(f"{bid} {room}")
  sys.stdout.write("\\n".join(out) + "\\n")
if \_\_name\_\_ == "\_\_main\_\_":
  main()
Wait, let me double-check the date comparison. Dates are in YYYY-MM-DD format, which sorts lexicographically the same as chronologically. So string comparison works fine.
Let me verify the logic once more:
occupied\[0]\[0] <= checkin: room becomes free if its checkout date is on or before the new booking's checkin date. Since checkout happens before checkin on the same day, <= is correct.
Let me test with the example:
A1: checkin=2026-11-01. occupied empty. available empty. room=1, next\_room=2, room\_count=1. occupied=\[(2026-11-03,1)]
B2: checkin=2026-11-02. occupied\[0]=(2026-11-03,1), 2026-11-03 <= 2026-11-02? No. available empty. room=2, next\_room=3, room\_count=2. occupied=\[(2026-11-03,1),(2026-11-04,2)]
C3: checkin=2026-11-03. occupied\[0]=(2026-11-03,1), 2026-11-03 <= 2026-11-03? Yes. Pop, available=\[1]. occupied\[0]=(2026-11-04,2), 2026-11-04 <= 2026-11-03? No. Assign room 1. occupied=\[(2026-11-04,2),(2026-11-05,1)]
D4: checkin=2026-11-04. occupied\[0]=(2026-11-04,2), <= 2026-11-04? Yes. Pop, available=\[2]. occupied\[0]=(2026-11-05,1), <= 2026-11-04? No. Assign room 2.
Output:
text
2
A1 1
B2 2
C3 1
D4 2
✓ Matches expected output.
Complexity: O(n log n) time, O(n) space. Handles 100k easily.
Edge case: room\_count is correctly maintained since we only increment when we need a brand new room number.
The solution looks correct. Let me finalize it.
أGemini
Here is a complete, single-file Python 3.11+ solution that solves the room allocation problem using a min-heap to assign the smallest available room number deterministically and efficiently.Python 3.11+ SolutionPythonimport sys
import heapq
def main():
  input\_data = sys.stdin.read().splitlines()
  if not input\_data:
  return
  n = int(input\_data\[0].strip())
  if n == 0:
  print(0)
  return
  bookings = \[]
  for idx in range(n):
  line = input\_data\[idx + 1].strip()
  if not line:
  continue
  b\_id, checkin, checkout = line.split()
  # ISO date strings (YYYY-MM-DD) compare correctly lexicographically
  bookings.append((checkin, checkout, idx, b\_id))
  # Sort bookings chronologically by check-in date
  # Retain original index to restore output order
  bookings.sort(key=lambda x: x\[0])
  # Min-heap tracking active room assignments: (checkout\_date, assigned\_room\_number)
  active\_rooms = \[]
 
  # Min-heap tracking available room numbers freed up by past checkouts
  free\_room\_numbers = \[]
  total\_rooms\_used = 0
  assigned\_rooms = \[0] \* n
  for checkin, checkout, original\_idx, b\_id in bookings:
  # Free up any rooms whose previous occupants checked out on or before this booking's checkin date
  while active\_rooms and active\_rooms\[0]\[0] <= checkin:
  \_, freed\_room = heapq.heappop(active\_rooms)
  heapq.heappush(free\_room\_numbers, freed\_room)
  # Assign the smallest available room number
  if free\_room\_numbers:
  assigned\_room = heapq.heappop(free\_room\_numbers)
  else:
  total\_rooms\_used += 1
  assigned\_room = total\_rooms\_used
  assigned\_rooms\[original\_idx] = (b\_id, assigned\_room)
  heapq.heappush(active\_rooms, (checkout, assigned\_room))
  # Output results
  print(total\_rooms\_used)
  for b\_id, room\_num in assigned\_rooms:
  print(f"{b\_id} {room\_num}")
if \_\_name\_\_ == '\_\_main\_\_':
  main()
Key Highlights \& PerformanceDate Comparison: Since dates are formatted as YYYY-MM-DD, standard string comparison produces the correct chronological order without the overhead of parsing datetime objects.Min-Heap Algorithm:active\_rooms stores end-dates sorted min-first to quickly release expired room reservations in $\\mathcal{O}(\\log k)$ time.free\_room\_numbers ensures that among all unoccupied rooms, the smallest room number is always selected next.Complexity \& Execution Time:Time Complexity: $\\mathcal{O}(N \\log N)$ due to initial sorting and heap operations, easily processing 100,000 bookings in under 0.3 seconds.Space Complexity: $\\mathcal{O}(N)$ to store array allocations and heap entries.