{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "90ffdccd",
   "metadata": {},
   "source": [
    "*Interval Request Scheduling* -- Greedy Algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "66ae47a2",
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "# random pair (s, f) where s and f are integers between\n",
    "# 0 and 99, inclusive\n",
    "def random_request():\n",
    "    return tuple(sorted(random.sample(range(0, 100), 2)))\n",
    "\n",
    "# make n random requests and return them all\n",
    "def make_requests(n):\n",
    "    #requests = []\n",
    "    #for i in range(n):\n",
    "    #    requests.append(random_request())\n",
    "    #return requests\n",
    "    return [random_request() for i in range(n)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "8bf45251",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(12, 72)"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "random_request()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "630b680c",
   "metadata": {},
   "source": [
    "random_request()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "5636e205",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(25, 71),\n",
       " (27, 75),\n",
       " (33, 94),\n",
       " (31, 66),\n",
       " (22, 98),\n",
       " (24, 76),\n",
       " (15, 54),\n",
       " (89, 91),\n",
       " (0, 99),\n",
       " (4, 31)]"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "make_requests(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "014186ce",
   "metadata": {},
   "outputs": [],
   "source": [
    "def plot_requests(requests):\n",
    "    # sort the requests\n",
    "    # plot one per line\n",
    "    \n",
    "    sorted_requests = sorted(requests, key=lambda x : x[1])\n",
    "    \n",
    "    for r in sorted_requests:\n",
    "        # r is one tuple (start, end)\n",
    "        print(\" \"*(r[0]) + \"-\"*(r[1]-r[0]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "615c0a64",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[(21, 70), (46, 73), (3, 99), (58, 77), (68, 71), (31, 65), (65, 82), (24, 76), (20, 65), (29, 80)]\n",
      "                               ----------------------------------\n",
      "                    ---------------------------------------------\n",
      "                     -------------------------------------------------\n",
      "                                                                    ---\n",
      "                                              ---------------------------\n",
      "                        ----------------------------------------------------\n",
      "                                                          -------------------\n",
      "                             ---------------------------------------------------\n",
      "                                                                 -----------------\n",
      "   ------------------------------------------------------------------------------------------------\n"
     ]
    }
   ],
   "source": [
    "R = make_requests(10)\n",
    "print(R)\n",
    "plot_requests(R)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "id": "1acbf0d2",
   "metadata": {},
   "outputs": [],
   "source": [
    "def greedy_solution(requests):\n",
    "    sorted_requests = sorted(requests, key=lambda x: x[1])\n",
    "    # O(n * log(n))\n",
    "    solution = []\n",
    "    \n",
    "    # remove the thing at index 0 from sorted_requests\n",
    "    # AND append to solution, in one line\n",
    "    solution.append(sorted_requests.pop(0))\n",
    "    \n",
    "    while len(sorted_requests) > 0:\n",
    "        request = sorted_requests.pop(0)\n",
    "        \n",
    "        # if the start time of request is > the end\n",
    "        # time of the latest meeting I've accepted:\n",
    "        if request[0] >= solution[-1][1]:\n",
    "            solution.append(request)\n",
    "    \n",
    "    return solution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "id": "ea589576",
   "metadata": {},
   "outputs": [],
   "source": [
    "requests = make_requests(100)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "id": "b2fdd6ec",
   "metadata": {},
   "outputs": [],
   "source": [
    "greedy_sol = greedy_solution(requests)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "id": "fa2c92e7",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(greedy_sol)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "id": "823667e1",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[(2, 10), (17, 24), (31, 32), (39, 40), (43, 44), (53, 67), (67, 69), (70, 80), (81, 87), (90, 95)]\n"
     ]
    }
   ],
   "source": [
    "print(greedy_sol)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d34a242f",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "id": "19e18121",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "  --------\n",
      "                 -------\n",
      "                               -\n",
      "                                       -\n",
      "                                           -\n",
      "                                                     --------------\n",
      "                                                                   --\n",
      "                                                                      ----------\n",
      "                                                                                 ------\n",
      "                                                                                          -----\n"
     ]
    }
   ],
   "source": [
    "plot_requests(greedy_sol)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "id": "bedc5644",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(greedy_sol)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "bb48c814",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}