{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "6c920d74df4d",
   "metadata": {},
   "source": [
    "# Meeting Rooms II\n",
    "\n",
    "| Field      | Value                                   |\n",
    "|------------|-----------------------------------------|\n",
    "| Source     | [link](https://leetcode.com/problems/meeting-rooms-ii/)  |\n",
    "| Difficulty | Medium                    |\n",
    "| Topics     | `array`, `sorting`, `two pointers`, `sweep line`, `heap`                     |\n",
    "| Date       | 2026-10-13                              |\n",
    "| Status     | Solved                                  |"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "139378d524f9",
   "metadata": {},
   "source": [
    "## 1. Problem\n",
    "\n",
    "> *From a coding assessment (2026-10-13), where it was called \"Minimum meeting rooms\". Same\n",
    "> problem as LeetCode #253 Meeting Rooms II.*\n",
    ">\n",
    "> Given `n` meetings as `[start, end]`, return the minimum number of rooms so that no two\n",
    "> meetings in the same room overlap. A meeting ending at time `t` and one starting at `t` do\n",
    "> **not** overlap, so they can share a room.\n",
    "\n",
    "**Example 1**\n",
    "```\n",
    "Input:  meetingTimings = [[1, 4], [1, 5], [5, 6], [6, 10], [7, 9]]\n",
    "Output: 2\n",
    "```\n",
    "\n",
    "**Constraints**\n",
    "- `1 <= n <= 2 * 10^5`\n",
    "- `1 <= start <= end <= 2 * 10^6`"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4b3b539cdf6f",
   "metadata": {},
   "source": [
    "## 2. Thinking\n",
    "\n",
    "- **Brute force idea:** the busiest moment is always at some meeting's start, so for each start\n",
    "  `s` count the meetings with `start <= s < end`: $O(n^2)$. Too slow at $n = 2 \\cdot 10^5$.\n",
    "- **Key insight:** every meeting running at the same moment needs its own room, and rooms can be\n",
    "  reused freely, so **answer = peak number of overlapping meetings**. To find the peak you don't\n",
    "  need to know which start goes with which end: two sorted timelines are enough, one for \"a\n",
    "  meeting begins\" and one for \"a room frees up\". Sweep them with two pointers.\n",
    "- **Tie rule:** a meeting ending at 5 hands its room to one starting at 5, so at equal times the\n",
    "  **end is processed first** (`ends[j] <= s`, not `<`).\n",
    "- **Edge cases to remember:** a single meeting, touching meetings (`[1,5]`, `[5,6]` → 1 room),\n",
    "  identical meetings (all need separate rooms), one long meeting covering many short ones.\n",
    "  **Zero-length meetings** (`start == end`, allowed by the constraints) are ambiguous: the sweep\n",
    "  treats them as needing no room, the heap gives them one (see section 5)."
   ]
  },
  {
   "cell_type": "code",
   "id": "80a110c1ba4d",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "# Setup: run this cell first. Lets you run pytest tests inside the notebook.\n",
    "try:\n",
    "    import ipytest\n",
    "except ImportError:  # Colab and other fresh kernels don't ship ipytest\n",
    "    %pip install -q ipytest\n",
    "    import ipytest\n",
    "import pytest\n",
    "\n",
    "ipytest.autoconfig()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "27a19609c21c",
   "metadata": {},
   "source": [
    "## 3. Solution\n",
    "\n",
    "### Approach A — my version: sorted starts and ends, two pointers ✅ best practice\n",
    "\n",
    "**Complexity:** Time $O(n \\log n)$ (sorting; the loop is $O(n)$ because `j` only moves forward)\n",
    "· Space $O(n)$.\n",
    "`j` points at the earliest meeting that hasn't ended yet. For each start, release every meeting\n",
    "with `end <= s`, then take a room for the new one and record the peak."
   ]
  },
  {
   "cell_type": "code",
   "id": "8f9513fb4856",
   "metadata": {},
   "source": [
    "def min_meeting_rooms(meetings: list[list[int]]) -> int:\n",
    "    starts = sorted(m[0] for m in meetings)\n",
    "    ends = sorted(m[1] for m in meetings)\n",
    "\n",
    "    rooms = max_rooms = j = 0\n",
    "    for s in starts:\n",
    "        # free every room whose meeting ended by this start time\n",
    "        while j < len(ends) and ends[j] <= s:\n",
    "            j += 1\n",
    "            rooms -= 1\n",
    "        rooms += 1\n",
    "        max_rooms = max(max_rooms, rooms)\n",
    "    return max_rooms"
   ],
   "execution_count": null,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "id": "4158c3bd6edd",
   "metadata": {},
   "source": [
    "### Approach B — brute force: count overlaps at every start\n",
    "\n",
    "**Complexity:** Time $O(n^2)$ · Space $O(1)$.\n",
    "The peak is reached at some start time, so check each one. Only useful as a reference to test\n",
    "the others against."
   ]
  },
  {
   "cell_type": "code",
   "id": "12992cb9409b",
   "metadata": {},
   "source": [
    "def min_meeting_rooms_brute(meetings: list[list[int]]) -> int:\n",
    "    return max(sum(a <= s < b for a, b in meetings) for s, _ in meetings)"
   ],
   "execution_count": null,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "id": "4adf9509cf58",
   "metadata": {},
   "source": [
    "### Approach C — sort by start, min-heap of end times\n",
    "\n",
    "**Complexity:** Time $O(n \\log n)$ · Space $O(n)$.\n",
    "The heap holds the end time of every room in use. If the room that frees up earliest is free by\n",
    "this start, reuse it (pop), then push this meeting's end. The heap's final size is the answer.\n",
    "Same speed, slightly more code, and it extends naturally to \"which room does each meeting get\"."
   ]
  },
  {
   "cell_type": "code",
   "id": "b2dd2a7b6acc",
   "metadata": {},
   "source": [
    "import heapq\n",
    "\n",
    "def min_meeting_rooms_heap(meetings: list[list[int]]) -> int:\n",
    "    ends: list[int] = []                     # end times of rooms in use\n",
    "    for start, end in sorted(meetings):\n",
    "        if ends and ends[0] <= start:        # earliest-ending room is free again\n",
    "            heapq.heapreplace(ends, end)\n",
    "        else:\n",
    "            heapq.heappush(ends, end)\n",
    "    return len(ends)"
   ],
   "execution_count": null,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "id": "b1b051b546e6",
   "metadata": {},
   "source": [
    "## 4. Tests\n",
    "\n",
    "Every approach runs against every case. All cases have `start < end`; zero-length meetings are\n",
    "looked at separately in section 5 because the approaches disagree on them."
   ]
  },
  {
   "cell_type": "code",
   "id": "cfebdefb51f0",
   "metadata": {},
   "source": [
    "%%ipytest -q\n",
    "\n",
    "APPROACHES = [\n",
    "    min_meeting_rooms,\n",
    "    min_meeting_rooms_brute,\n",
    "    min_meeting_rooms_heap,\n",
    "]\n",
    "\n",
    "CASES = [\n",
    "    ([[1, 4], [1, 5], [5, 6], [6, 10], [7, 9]], 2),\n",
    "    ([[1, 2]], 1),                                   # single meeting\n",
    "    ([[1, 5], [5, 6], [6, 7]], 1),                   # touching: end == start shares a room\n",
    "    ([[1, 5], [4, 6]], 2),                           # overlap by one unit\n",
    "    ([[2, 3], [2, 3], [2, 3]], 3),                   # identical meetings\n",
    "    ([[1, 100], [2, 3], [4, 5], [6, 7]], 2),         # one long meeting over short ones\n",
    "    ([[7, 10], [2, 4]], 1),                          # unsorted input, no overlap\n",
    "    ([[0, 30], [5, 10], [15, 20]], 2),               # LeetCode #253 example 1\n",
    "    ([[1, 10], [2, 9], [3, 8], [4, 7]], 4),          # nested: all overlap at 4\n",
    "]\n",
    "\n",
    "@pytest.mark.parametrize(\"fn\", APPROACHES)\n",
    "@pytest.mark.parametrize(\"meetings, expected\", CASES)\n",
    "def test_min_meeting_rooms(fn, meetings, expected):\n",
    "    assert fn(meetings) == expected"
   ],
   "execution_count": null,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "id": "fa5b16f32488",
   "metadata": {},
   "source": [
    "## 5. Scratch / Experiments\n",
    "\n",
    "### Zero-length meetings\n",
    "\n",
    "The constraints allow `start == end`. The sweep processes the end before the start at equal\n",
    "times, so a zero-length meeting gives its room back before taking it: it never counts. The heap\n",
    "always pushes it, so it gets a room. If the grader expects a room for every meeting, use the heap."
   ]
  },
  {
   "cell_type": "code",
   "id": "93fe0269eba7",
   "metadata": {},
   "source": [
    "for meetings in ([[5, 5]], [[5, 5], [5, 5]], [[1, 10], [5, 5]]):\n",
    "    print(meetings, {fn.__name__: fn(meetings) for fn in APPROACHES})"
   ],
   "execution_count": null,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "id": "273b8211feee",
   "metadata": {},
   "source": [
    "### Timing\n",
    "\n",
    "Max size $n = 2 \\cdot 10^5$ random meetings for A and C; the brute force is $O(n^2)$, so it gets\n",
    "$n = 2000$, where it is already ~400× slower than the others.\n",
    "\n",
    "Typical results:\n",
    "\n",
    "| Approach | $n = 2000$ | $n = 2 \\cdot 10^5$ |\n",
    "|---|---|---|\n",
    "| A two pointers ✅ | ~0.5 ms | ~100 ms |\n",
    "| B brute force | ~190 ms | (~30 min) |\n",
    "| C min-heap | ~0.5 ms | ~190 ms |\n",
    "\n",
    "A and C are both $O(n \\log n)$ and tie at small $n$. At full size A is about twice as fast: it sorts two flat lists of ints\n",
    "(fast C comparisons) while C sorts lists of pairs (each comparison compares lists) and then does\n",
    "a Python-level heap operation per meeting."
   ]
  },
  {
   "cell_type": "code",
   "id": "4046ecf70c5b",
   "metadata": {},
   "source": [
    "import random\n",
    "\n",
    "random.seed(0)\n",
    "def random_meetings(n):\n",
    "    out = []\n",
    "    for _ in range(n):\n",
    "        s = random.randint(1, 2_000_000 - 1)\n",
    "        out.append([s, random.randint(s + 1, min(s + 50_000, 2_000_000))])\n",
    "    return out\n",
    "\n",
    "small, big = random_meetings(2000), random_meetings(200_000)\n",
    "for fn in APPROACHES:\n",
    "    print(f\"{fn.__name__:26s} n=2000 \", end=\" \")\n",
    "    %timeit fn(small)\n",
    "for fn in (min_meeting_rooms, min_meeting_rooms_heap):\n",
    "    print(f\"{fn.__name__:26s} n=2e5  \", end=\" \")\n",
    "    %timeit fn(big)"
   ],
   "execution_count": null,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "id": "67f76849c74f",
   "metadata": {},
   "source": [
    "## 6. Takeaways\n",
    "\n",
    "- **Pattern:** \"how many things are active at the same time\" / \"minimum resources so nothing\n",
    "  clashes\" → **peak overlap**. Sort the start times and the end times separately and sweep with\n",
    "  two pointers (or sort ±1 events). Pairing doesn't matter, only the order of events. Decide the\n",
    "  **tie rule** explicitly: end-before-start when touching intervals don't overlap.\n",
    "- **Mistakes to avoid:**\n",
    "  - Using `<` instead of `<=` when releasing rooms: touching meetings would then need two rooms.\n",
    "  - Assuming the input is sorted: both approaches sort first.\n",
    "  - Not checking what the constraints allow: `start <= end` means zero-length meetings exist,\n",
    "    and the sweep and the heap answer them differently.\n",
    "- **Alternatives:** the min-heap (Approach C) when you also need to assign rooms; a difference\n",
    "  array over the time range ($O(n + T)$, $T = 2 \\cdot 10^6$) when times are small integers.\n",
    "- **Related problems:** Meeting Rooms (#252, can one person attend all = peak ≤ 1), Merge\n",
    "  Intervals (#56, sort by start), Non-overlapping Intervals (#435, greedy by end), Car Pooling\n",
    "  (#1094, same sweep with passenger counts), My Calendar II (#731), Minimum Number of Arrows to\n",
    "  Burst Balloons (#452)."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}