Chapter_16_Greedy_Algorithm/exercises_16.1.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 16.1 An activity-selection problem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 16.1-1\n",
    "\n",
    "> Give a dynamic-programming algorithm for the activity-selection problem, based on recurrence (16.2). Have your algorithm compute the sizes $c[i, j]$ as defined above and also produce the maximum-size subset of mutually compatible activities.\n",
    ">\n",
    "> Assume that the inputs have been sorted as in equation (16.1). Compare the running time of your solution to the running time of GREEDY-ACTIVITY-SELECTOR."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$O(n^3)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 16.1-2\n",
    "\n",
    "> Suppose that instead of always selecting the first activity to finish, we instead select the last activity to start that is compatible with all previously selected activities. Describe how this approach is a greedy algorithm, and prove that it yields an optimal solution."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The same."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 16.1-3\n",
    "\n",
    "> Not just any greedy approach to the activity-selection problem produces a maximum-size set of mutually compatible activities. Give an example to show that the approach of selecting the activity of least duration from among those that are compatible with previously selected activities does not work. Do the same for the approaches of always selecting the compatible activity that overlaps the fewest other remaining activities and always selecting the compatible remaining activity with the earliest start time."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Least duration: [1, 5], [4, 7], [6, 10]\n",
    "\n",
    "Overlap fewest: [1, 4], [5, 7], [8, 10], [1, 2], [3, 5], [6, 8], [9, 10], ...\n",
    "\n",
    "Earliest start: [1, 6], [5, 10], [2, 4]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 16.1-4\n",
    "\n",
    "> Suppose that we have a set of activities to schedule among a large number of lecture halls, where any activity can take place in any lecture hall. We wish to schedule all the activities using as few lecture halls as possible. Give an efficient greedy algorithm to determine which activity should use which lecture hall.\n",
    "\n",
    "> (This problem is also known as the __*interval-graph coloring problem*__. We can create an interval graph whose vertices are the given activities and whose edges connect incompatible activities. The smallest number of colors required to color every vertex so that no two adjacent vertices have the same color corresponds to finding the fewest lecture halls needed to schedule all of the given activities.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Sort the intervals by start time, if the start time of one interval is the same as the finish time of the other interval, we should assume the finish time is less than the start time. From left to right, add 1 when there is a start time and subtract 1 when there is a finish time, the number of halls needed is the maximum number of the count."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 16.1-5\n",
    "\n",
    "> Consider a modification to the activity-selection problem in which each activity $a_i$ has, in addition to a start and finish time, a value $v_i$. The objective is no longer to maximize the number of activities scheduled, but instead to maximize the total value of the activities scheduled. That is, we wish to choose a set $A$ of compatible activities such that $\\sum_{a_k \\in A} v_k$ is maximized. Give a polynomial-time algorithm for this problem."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let $dp[i]$ be the maximum total value before time $i$,\n",
    "\n",
    "$$\n",
    "dp[i] = \\max(dp[i-1], \\max_{f_j \\le i} dp[s_j] + v_j)\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def activity_selection(s, f, v):\n",
    "    dp = {}\n",
    "    n = len(s)\n",
    "    last = None\n",
    "    for i in sorted(list(set(s + f))):\n",
    "        if last is None:\n",
    "            dp[i] = 0\n",
    "        else:\n",
    "            dp[i] = last\n",
    "            for j in range(n):\n",
    "                if f[j] <= i:\n",
    "                    dp[i] = max(dp[i], dp[s[j]] + v[j])\n",
    "        last = dp[i]\n",
    "    return last"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\Theta(n^2)$"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}