Greedy and Dynamic programming.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Greedy Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A greedy algorithm always makes the choice that looks best at the moment. That is, it makes a locally optimal choice in the hope that this choice will lead to a globally optimal solution."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Procedures:\n",
    "\n",
    "1. Determine the optimal substructure of the problem.\n",
    "2. Develop a recursive solution.\n",
    "3. Show that if we make the greedy choice,then only one subproblem remains.\n",
    "4. Prove that it is always safe to make the greedy choice.(Steps3 and 4 can occur in either order.)\n",
    "5. Develop a recursive algorithm that implements the greedy strategy.\n",
    "6. Convert the recursive algorithm to an iterative algorithm."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Design:\n",
    "\n",
    "1. Cast the optimization problem as one in which we make a choice and are left with one subproblem to solve.\n",
    "2. Prove that there is always an optimal solution to the original problem that makes the greedy choice, so that the greedy choice is always safe.\n",
    "3. Demonstrate optimal substructure by showing that, having made the greedy choice, what remains is a subproblem with the property that if we combine an optimal solution to the subproblem with the greedy choice we have made, we arrive at an optimal solution to the original problem."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## An activity selection problem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\\begin{array}{|l|l|l|l|l|l|l|l|l|l|l|l|}\n",
    "\\hline\n",
    "i & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\\\\n",
    "\\hline\n",
    "s_i &1&3&0&5&3&5&6&8&8&2&12 \\\\\n",
    "\\hline\n",
    "f_i &4&5&6&7&9&9&10&11&12&14&16 \\\\\n",
    "\\hline\n",
    "\\end{array}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The optimal substructure"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We denote $S_{i j}$ the set of activities that start after $a_i$ finishes and finishes before $a_j$ starts. Suppose we want to find a maximum set of mutually compatible activities in $S_{i j}$ and suppose further that such a maximum set is $A_{i j}$. This set will include some activity $a_k$. By including $a_k$ in an optimal solution, we are left with two subproblems: finding mutually compatible activities in the set $S_{i k}$ (activities that start after activity $a_i$ finishes and that finish before activity $a_k$ starts) and finding mutually compatible activities in the set $S_{kj}$ (activities that start after activity $a_k$ finishes and that finish before activity $a_j$ starts). We have\n",
    "\n",
    "$$\n",
    "A_{ij}=A_{ik} \\cup \\{a_k\\} \\cup A_{kj}\n",
    "$$\n",
    "\n",
    "So the maximum size set $A_{i j}$ of mutually compatible activities in $S_{ij}$ consists of \n",
    "\n",
    "$$\n",
    "\\mid A_{i j} \\mid=\\mid A_{ik} \\mid+1+\\mid A_{k j} \\mid\n",
    "$$\n",
    "\n",
    "It can be shown that the optimal solution $A_{i j}$ must also include optimal solutions to the two subproblems for $S_{i k}$ and $S_{k j}$. The argument is as follows: If we could find a set $A_{k j}^{'}$ of mutually compatible activities in $S_{k j}$ where $\\mid A_{k j}^{'} \\mid > \\mid A_{k j} \\mid$, then we would have constructed a set of $\\mid A_{ik} \\mid+1+\\mid A_{k j}^{'} \\mid>\\mid A_{ik} \\mid+1+\\mid A_{k j} \\mid=\\mid A_{ij} \\mid$ mutually compatible activities, which contradicts the assumption that $A_{i j}$ is optimal."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As a result, we could solve the activity-selection problem by dynamic programming. If we denote the size of an optimal solution for the set $S_{i j}$ by $c[i,j]$, then we would have the recurrence\n",
    "\n",
    "$$\n",
    "c[i,j]=c[i,k]+c[k,j]+1\n",
    "$$\n",
    "\n",
    "Since we do not know whether $A_{i j}$ will include $a_k$, we have to examine all $a_k$ in $S_{i j}$.\n",
    "\n",
    "$$\n",
    "c[i,j]=\\Big\\{ \\begin{array}{ll}\n",
    "                  0 & S_{i j}=\\phi \\\\\n",
    "                  \\underset{a_k \\in S_{i j}}{max}\\{ c[i,k]+c[k,j]+1 \\} & S_{ij} \\neq \\phi\\\\\n",
    "                \\end{array}\n",
    "$$\n",
    "\n",
    "We could then develop a recursive algorithm and memoize it, or we could work bottom-up and fill in table entries as we go along. But we would be overlooking another important characteristic of the activity-selection problem that we can use to great advantage."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Making the greedy choice"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The greedy choice is to choose the activity that finishes first to leave as much time as possible for other activities. If we make the greedy choice, we only need to solve one remaining subproblem: finding activities that start after $a_1$ finishes. Let $S_k=\\{ a_i \\in S: s_i >= f_k \\}$ be the set of activities that start after $a_k$ finishes. If we make the greedy choice of activity $a_1$, then $S_1$ remains as the only subproblem to solve. Optimal substructure tells us that if $a_1$ is in the optimal solution, then an optimal solution to the original problem consists of activity $a_1$ and all the activities in an optimal solution to the subproblem $S_1$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Correctness of greedy choice"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Consider any nonempty subproblem $S_k$, and let $a_m$ be an activity in $S_k$ with the earliest finish time. Then $a_m$ is included in some maximum-size subset of mutually compatible activities of $S_k$.\n",
    "\n",
    "**Proof**: Let $a_j$ is the activity in $A_k$ with the earliest finish time. If $a_j \\neq a_m$, we could always replace $a_j$ with $a_m$ to construct our new $A_k^{'}$ such that $\\mid A_k^{'} \\mid=\\mid A_k \\mid$ since by definition $f_m \\leq f_j$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### A recursive greedy algorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In order to start, we add the fictitious activity $a_0$ with $f_0=0$, so that subproblem $S_0$ is the entire set of activities $S$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def rec_act_selector(start,finish,k,n):\n",
    "    \"\"\"\n",
    "    :type start: List[int]\n",
    "    :type finish: List[int]\n",
    "    :type k: int\n",
    "    :type n: int\n",
    "    :rtype: List[int]\n",
    "    \"\"\"\n",
    "    m=k+1\n",
    "    # notice that the events are already sorted in finish time\n",
    "    while m<=n and start[m]<finish[k]:\n",
    "        m+=1\n",
    "    if m<=n:\n",
    "        return [m]+rec_act_selector(start,finish,m,n)\n",
    "    else:\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 4, 8, 11]"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "start=[1,3,0,5,3,5,6,8,8,2,12]\n",
    "finish=[4,5,6,7,9,9,10,11,12,14,16]\n",
    "a0=[0]\n",
    "rec_act_selector(a0+start,a0+finish,0,len(start))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### An iterative greedy algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def iter_act_selector(start,finish):\n",
    "    \"\"\"\n",
    "    :type start: List[int]\n",
    "    :type finish: List[int]\n",
    "    :type k: int\n",
    "    :type n: int\n",
    "    :rtype: List[int]\n",
    "    \"\"\"\n",
    "    m=0\n",
    "    # artificially set a_0 finish time at 0 so that it is smaller than start[i],i=0,1,...\n",
    "    last_finish=0\n",
    "    optimal_solution=[]\n",
    "    # notice that the events are already sorted in finish time\n",
    "    while m<len(start):\n",
    "        if start[m]<last_finish:\n",
    "            m+=1\n",
    "        else:\n",
    "            last_finish=finish[m]\n",
    "            optimal_solution.append(m)\n",
    "            m+=1\n",
    "    return optimal_solution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 3, 7, 10]"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "start=[1,3,0,5,3,5,6,8,8,2,12]\n",
    "finish=[4,5,6,7,9,9,10,11,12,14,16]\n",
    "iter_act_selector(start,finish)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Minimal Spanning Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given an undirected graph G=(V,E) and a cost $c_e$ for each edge $e$. Find the minimum cost tree $T$ in E that spans all vertices.\n",
    "\n",
    "Note:\n",
    "\n",
    "1. T has no cycles.\n",
    "2. The subgraph (V,T) is connected."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### PRIM'S MINIMUM SPANNING TREE ALGORITHM"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Initialize X=[s] with s in vertices chosen arbitrarily.\n",
    "\n",
    "* T=empty tree\n",
    "\n",
    "* while $X!=V$:\n",
    "\n",
    "      Let e = (u,v) be the cheapest edge of G with u ∈ X, v ∈/ X.\n",
    "      \n",
    "      Add e to T.\n",
    "      \n",
    "      Add v to X.\n",
    "      \n",
    "Runtime analysis: n-1 loops, m edges in each loop, the total is O(m n)\n",
    "\n",
    "**Implementation with heap**:\n",
    "\n",
    "* Initialize X=[s] with s in vertices chosen arbitrarily.\n",
    "\n",
    "* T=empty tree\n",
    "\n",
    "* key[v]=cheapest edge (u,v) for u in X, where v in V-X (in the heap)\n",
    "\n",
    "* while $X!=V$:\n",
    "\n",
    "      Extract min v = e = (u,v) be the cheapest edge of G with u ∈ X, v ∈/ X in the heap\n",
    "\n",
    "      for each edge (v, w) with w in V-X(in the heap):\n",
    "       \n",
    "          delete w from heap\n",
    "          recompute key[w]=min{key[w],c_{vw}}\n",
    "          reinsert into the heap\n",
    "      \n",
    "      add (u,v) to T.\n",
    "      \n",
    "      add v to X.\n",
    "      \n",
    "Runtime: n-1 loops. In each loop, extract min O(log n). On the otherhand, there are in total O(m log(n)) time for decrease key. As m>=n-1 since G is connected, the total runtime is O(m log (n))."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### KRUSKAL'S MINIMUM SPANNING TREE ALGORITHM"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## HUFFMAN CODES"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "Goal: Best binary prefix-free encoding for a given set of character frequencies.\n",
    "\n",
    "Useful fact: Binary codes ↔ Binary trees\n",
    "\n",
    "Prefix-free ↔ Labelled nodes = the leaves\n",
    "\n",
    "Input: Probability pi for each character i ∈ Σ.\n",
    "\n",
    "Notation: If T = tree with leaves ↔ symbols of Σ, then average\n",
    "encoding length L(T) =  \\sum_{i ∈ \\Sigma} pi · [depth of i in T]\n",
    "\n",
    "Output: A binary tree T minimizing the average encoding length L(·)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Dynamic programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We typically apply dynamic programming to optimization problems. Such prob- lems can have many possible solutions. Each solution has a value, and we wish to find a solution with the optimal (minimum or maximum) value. We call such a solution an optimal solution to the problem, as opposed to the optimal solution, since there may be several solutions that achieve the optimal value."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Steps:\n",
    "\n",
    "1. Characterize the structure of an optimal solution.\n",
    "2. Recursively define the value of an optimal solution.\n",
    "3. Compute the value of an optimal solution,typically in a bottom-up fashion.\n",
    "4. Construct an optimal solution from computed information.\n",
    "\n",
    "If we need only the value of an optimal solution, and not the solution itself, then we can omit step 4. When we do perform step 4, we sometimes maintain additional information during step 3 so that we can easily construct an optimal solution."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Elements of dynamic programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Optimal substructure"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Overlapping subproblems"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Reconstructing an optimal solution"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Memoization"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Rod cutting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a rod of length $n$ inches and a table of prices $p_i$ for $i=1,2,...,n$, determine the maximum revenue $r_n$ obtainable by cutting up the rod and selling the pieces. Note that if the price $p_n$ for a rod of length $n$ is large enough, an optimal solution may require no cutting at all.\n",
    "\n",
    "\\begin{array}{|l|l|l|l|l|l|l|l|l|l|l|}\n",
    "\\hline\n",
    "length\\ i & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\\\\n",
    "\\hline\n",
    "price\\ p_i &1&5&8&9&10&17&17&20&24&30 \\\\\n",
    "\\hline\n",
    "\\end{array}\n",
    "\n",
    "If an optimal solution cuts the rod into $k$ pieces, for some $1 \\leq k \\leq n$, then an optimal decomposition\n",
    "\n",
    "$$\n",
    "n=i_1+i_2+...+i_k\n",
    "$$\n",
    "\n",
    "provides maximum corresponding revenue:\n",
    "\n",
    "$$\n",
    "r_n=p_{i_1}+p_{i_2}+...+p_{i_k}\n",
    "$$\n",
    "\n",
    "For our sample problem,\n",
    "\n",
    "* $r_1=1$ from solution $1=1$ (no cuts)\n",
    "* $r_2=5$ from solution $2=2$ (no cuts)\n",
    "* $r_3=8$ from solution $3=3$ (no cuts)\n",
    "* $r_4=10$ from solution $4=2+2$\n",
    "* $r_5=13$ from solution $5=2+3$\n",
    "* $r_6=17$ from solution $6=6$ (no cuts)\n",
    "* $r_7=18$ from solution $7=1+6$\n",
    "* $r_8=22$ from solution $8=2+6$\n",
    "* $r_9=25$ from solution $9=3+6$\n",
    "* $r_{10}=30$ from solution $10=10$ (no cuts)\n",
    "\n",
    "More generally, we can compute $r_n$ by\n",
    "\n",
    "$$\n",
    "r_n=max(p_n, r_1+r_{n-1}, r_2+r_{n-2},...,r_{n-1}+r_1)\n",
    "$$\n",
    "\n",
    "This recursion relation implies that in solving the original problem of size $n$, we solve smaller problems of the same type. This is called **optimal substructure**. The above recursion is a bit overcomplicated. In a related but slightly simpler way to arrange a recursive structure:\n",
    "\n",
    "$$\n",
    "r_n=\\underset{1 \\leq i \\leq n}{max}(p_i+r_{n-i})\n",
    "$$\n",
    "\n",
    "where $r_0=0$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Recursive top-down implementation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The recursive approach is based on\n",
    "\n",
    "$$\n",
    "r_n=\\underset{1 \\leq i \\leq n}{max}(p_i+r_{n-i})\n",
    "$$\n",
    "\n",
    "where $r_0=0$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def cut_rod(p,n):\n",
    "    \"\"\"\n",
    "    :type p: List[int]\n",
    "    :type n: int\n",
    "    :rtype: int\n",
    "    \"\"\"\n",
    "    if n==0:\n",
    "        return 0\n",
    "    else:\n",
    "        return max([p[i]+cut_rod(p,n-i-1) for i in range(n)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 140,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "107"
      ]
     },
     "execution_count": 140,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "p=[1,5,8,9,10,17,17,20,24,30,32,40,55,55,70,90,91,92,93,94,95,96]\n",
    "cut_rod(p,22)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The recursive implementation is very inefficient. The reason is because it solves the same subproblems repeatedly. We could analyze the runtime as follows: Let $T(n)$ denote the total number of calls made to cut_rod with length $n$. This expression equals the number of nodes in a subtree whose root is labeled by $n$. Then\n",
    "\n",
    "$$\n",
    "T(0)=1\n",
    "$$\n",
    "\n",
    "as $r[0]=1$ and\n",
    "\n",
    "$$\n",
    "T(n)=1+\\sum_{j=0}^{n-1}T(j)\n",
    "$$\n",
    "\n",
    "The initial 1 is for the call at the root. Then as a result,\n",
    "\n",
    "$$\n",
    "T(n)=2^n\n",
    "$$\n",
    "\n",
    "which can be shown by induction."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Dynamical programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "By storing the results of the subproblems, it is possible to reduce the running time to $O(n^2)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**top-down with memoization**: The procedure is still recursive in a natural manner, but modified to save the result of each subproblem (usually in an array or hashtable). The procedure first checks to see whether it has previously solved this subproblem. If so, it returns the saved value, saving further computation at this level; if not, the procedure computes the value in the usual manner. We say that the recursive procedure has been **memoized**; it \"remembers\" what results it has computed previously."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 138,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def memoized_cut_rod(p,n):\n",
    "    \"\"\"\n",
    "    :type p: List[int]\n",
    "    :type n: int\n",
    "    :rtype: int\n",
    "    \"\"\"\n",
    "    r=[-1]*n\n",
    "    return memoized_cut_rod_aux(p,n,r)\n",
    "    \n",
    "def memoized_cut_rod_aux(p,n,r):\n",
    "    if n==0:\n",
    "        return 0\n",
    "    if r[n-1]>=0:\n",
    "        return r[n-1]\n",
    "    else:\n",
    "        r[n-1]=max([p[i]+memoized_cut_rod_aux(p,n-i-1,r) for i in range(n)])\n",
    "        return r[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 139,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "107"
      ]
     },
     "execution_count": 139,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "p=[1,5,8,9,10,17,17,20,24,30,32,40,55,55,70,90,91,92,93,94,95,96]\n",
    "memoized_cut_rod(p,22)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**bottom-up method** This approach typically depends on some natural notion of the “size” of a subproblem, such that solving any par- ticular subproblem depends only on solving “smaller” subproblems. We sort the subproblems by size and solve them in size order, smallest first. When solving a particular subproblem, we have already solved all of the smaller subproblems its solution depends upon, and we have saved their solutions. We solve each sub- problem only once, and when we first see it, we have already solved all of its prerequisite subproblems."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 141,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def bottom_up_cut_rod(p,n):\n",
    "    \"\"\"\n",
    "    :type p: List[int]\n",
    "    :type n: int\n",
    "    :rtype: int\n",
    "    \"\"\"\n",
    "    r=[-1]*(n+1)\n",
    "    r[0]=0\n",
    "    for i in xrange(1,n+1):\n",
    "        r[i]=max([p[j-1]+r[i-j] for j in range(1,i+1)])\n",
    "    return r[1:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 142,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1,\n",
       " 5,\n",
       " 8,\n",
       " 10,\n",
       " 13,\n",
       " 17,\n",
       " 18,\n",
       " 22,\n",
       " 25,\n",
       " 30,\n",
       " 32,\n",
       " 40,\n",
       " 55,\n",
       " 56,\n",
       " 70,\n",
       " 90,\n",
       " 91,\n",
       " 95,\n",
       " 98,\n",
       " 100,\n",
       " 103,\n",
       " 107]"
      ]
     },
     "execution_count": 142,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "p=[1,5,8,9,10,17,17,20,24,30,32,40,55,55,70,90,91,92,93,94,95,96]\n",
    "bottom_up_cut_rod(p,22)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Consider whether the following \"greedy\" algorithm works: Define the density of a rod of length $i$ to be $p_i/i$. The greedy strategy for a rod of length $n$ cuts off a first piece of length $i$, where $1\\leq i\\leq n$, having maximum density. It then continues by applying the greedy strategy to the remaining piece of length $n-i$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Matrix-chain multiplication"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Give a dynamic-programming algorithm for the activity-selection problem, based on recurrence\n",
    "\n",
    "$$\n",
    "c[i,j]=\\Big\\{ \\begin{array}{ll}\n",
    "                  0 & S_{i j}=\\phi \\\\\n",
    "                  \\underset{a_k \\in S_{i j}}{max}\\{ c[i,k]+c[k,j]+1 \\} & S_{ij} \\neq \\phi\\\\\n",
    "                \\end{array}\n",
    "$$\n",
    "\n",
    "Have your algorithm compute the sizes $c[i,j]$ as defined above and also produce the maximum-size subset of mutually compatible activities. Assume that the inputs have been sorted based on finish time."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: We first calculate $S_{ij}$, the set of activities that start after $a_i$ finishes and finishes before $a_j$ starts.\n",
    "\n",
    "$$\n",
    "S_{ij}=\\Big\\{\\begin{array}{ll}\n",
    "                  [] & i \\geq j \\\\\n",
    "                  S_{ij} & i < j \\\\\n",
    "                \\end{array}\n",
    "$$\n",
    "\n",
    "Then we apply the recurrence relation to calculate c[i,j]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def dyn_act_selector(self,start,finish):\n",
    "        n=len(start)\n",
    "        S=[[[] for i in range(n)] for j in range(n)]\n",
    "        A=[[[] for i in range(n)] for j in range(n)]\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1,n):\n",
    "                S[i][j]=[k for k in range(i+1,j) if start[k]>=finish[i] and finish[k]<=start[j]]\n",
    "        C=[[0 for i in range(n)] for j in range(n)]\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1,n):\n",
    "                C[i][j]=self.max_compatible_size(i,j,S)\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1,n):\n",
    "                A[i][j]=self.max_compatible(i,j,S)\n",
    "        return C,A\n",
    "        \n",
    "    # mutually compatible activities size between i and j\n",
    "    def max_compatible_size(self,i,j,S):\n",
    "        if S[i][j]==[]:\n",
    "            return 0\n",
    "        else:\n",
    "            max_size=0\n",
    "            max_index=None\n",
    "            for k in S[i][j]:\n",
    "                size=self.max_compatible_size(i,k,S)+self.max_compatible_size(k,j,S)+1\n",
    "                if size>max_size:\n",
    "                    max_size=size\n",
    "                    max_index=[k]\n",
    "            return max_size\n",
    "        \n",
    "    # mutually compatible activities between i and j\n",
    "    def max_compatible(self,i,j,S):\n",
    "        if S[i][j]==[]:\n",
    "            return []\n",
    "        else:\n",
    "            max_size=0\n",
    "            max_list=[]\n",
    "            for k in S[i][j]:\n",
    "                compatible_list=self.max_compatible(i,k,S)+[k]+self.max_compatible(k,j,S)\n",
    "                if len(compatible_list)>max_size:\n",
    "                    max_size=len(compatible_list)\n",
    "                    max_list=compatible_list\n",
    "            return max_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "([[0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 2],\n",
       "  [0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 2],\n",
       "  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],\n",
       "  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],\n",
       "  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
       "  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
       "  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
       "  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
       "  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
       "  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
       "  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]],\n",
       " [[[], [], [], [], [], [], [], [3], [3], [], [3, 7]],\n",
       "  [[], [], [], [], [], [], [], [3], [3], [], [3, 7]],\n",
       "  [[], [], [], [], [], [], [], [], [], [], [6]],\n",
       "  [[], [], [], [], [], [], [], [], [], [], [7]],\n",
       "  [[], [], [], [], [], [], [], [], [], [], []],\n",
       "  [[], [], [], [], [], [], [], [], [], [], []],\n",
       "  [[], [], [], [], [], [], [], [], [], [], []],\n",
       "  [[], [], [], [], [], [], [], [], [], [], []],\n",
       "  [[], [], [], [], [], [], [], [], [], [], []],\n",
       "  [[], [], [], [], [], [], [], [], [], [], []],\n",
       "  [[], [], [], [], [], [], [], [], [], [], []]])"
      ]
     },
     "execution_count": 80,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "start=[1,3,0,5,3,5,6,8,8,2,12]\n",
    "finish=[4,5,6,7,9,9,10,11,12,14,16]\n",
    "C,A=o.dyn_act_selector(start,finish)\n",
    "C,A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[0, 0, 0], [0, 0, 0], [0, 0, 0]]"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "C=[[0 for i in range(3)] for j in range(3)]\n",
    "C"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "max([1,2,3])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 3, 5, 7]"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a=[1,3,5,7]\n",
    "b=[i for i in a]\n",
    "b"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# Leetcode"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 45. <font color=red>Jump Game II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given an array of non-negative integers, you are initially positioned at the first index of the array.\n",
    "\n",
    "Each element in the array represents your maximum jump length at that position.\n",
    "\n",
    "Your goal is to reach the last index in the minimum number of jumps.\n",
    "\n",
    "For example:\n",
    "Given array A = [2,3,1,1,4]\n",
    "\n",
    "The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: An obvious solution is go backtracking to record the number of minimal jumps from every position to the last index. This algorithm will take O(n^2) time. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 314,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def jump(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n=len(nums)\n",
    "        # array keep track of minimal jumps to the end\n",
    "        r=[-1]*n\n",
    "        r[n-1]=0\n",
    "        for i in range(n)[::-1]:\n",
    "            canjump=False\n",
    "            min_jump=n-1-i\n",
    "            for j in range(i+1,n):\n",
    "                if i+nums[i]>=j and r[j]>=0:\n",
    "                    canjump=True\n",
    "                    if r[j]+1<min_jump:\n",
    "                        min_jump=r[j]+1\n",
    "                        \n",
    "            if canjump==True:\n",
    "                r[i]=min_jump\n",
    "                \n",
    "        return r[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 315,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 315,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.jump([2,3,1,1,4])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The above solution is TLE. Can we do better? Discussion solution: We start from the beginning and make the furthest next jump until the end."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 323,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def jump(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n=len(nums)\n",
    "        i=0\n",
    "        j=0\n",
    "        jump=0\n",
    "        while j<n-1:\n",
    "            next_max_pos=min(i+nums[i],n-1)\n",
    "            while j<=next_max_pos:\n",
    "                if j+nums[j]>i+nums[i]:\n",
    "                    i=j\n",
    "                j+=1\n",
    "            jump+=1\n",
    "        return jump"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 319,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def jump(self, nums):\n",
    "        i, j, steps = 0, 1, 0\n",
    "        while j < len(nums):\n",
    "            endj = min(nums[i]+i+1, len(nums))\n",
    "            while j < endj:\n",
    "                if nums[j] + j > nums[i] + i: i = j\n",
    "                j += 1\n",
    "            steps += 1\n",
    "        return steps"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 324,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 324,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.jump([2,3,1,1,0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 55. Jump Game"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given an array of non-negative integers, you are initially positioned at the first index of the array.\n",
    "\n",
    "Each element in the array represents your maximum jump length at that position.\n",
    "\n",
    "Determine if you are able to reach the last index.\n",
    "\n",
    "For example:\n",
    "\n",
    "A = [2,3,1,1,4], return true.\n",
    "\n",
    "A = [3,2,1,0,4], return false."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: First observation, the List can be converted into a tree structure, every reachable position from the current position are the children of the current node. Then we search all the way down to the leafs to find whether the last index is in the node of the tree."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 152,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def canJump(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if nums==[]:\n",
    "            return True\n",
    "        # assign the root\n",
    "        return self.canJumpAux(nums,0)\n",
    "    \n",
    "    def canJumpAux(self,nums,pos):\n",
    "        n=len(nums)\n",
    "        # assign the root\n",
    "        root=nums[pos]\n",
    "        # if the maximum jump reaches the end, return true\n",
    "        if pos+nums[pos]>=n-1:\n",
    "            return True\n",
    "        # search children\n",
    "        for i in range(pos+1,pos+nums[pos]+1):\n",
    "            if self.canJumpAux(nums,i):\n",
    "                return True\n",
    "            \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 154,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 154,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.canJump([2,3,1,1,4])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The above solution is TLE. Let me analyze the time complexity: In the worst case, that is last index is unreachable even when the whole list (except the last) is visited. For position n, let T(n) be the runtime,\n",
    "\n",
    "$$\n",
    "T(n)=1+\\sum_{i=1}^{nums[n]} T(n+i)\n",
    "$$\n",
    "\n",
    "In the worst case, $nums[n]=length-1-n$:\n",
    "\n",
    "$$\n",
    "T(n)=1+\\sum_{i=1}^{length-1-n} T(n+i) \\\\\n",
    "=1+\\sum_{i=n+1}^{length-1} T(i)\n",
    "$$\n",
    "\n",
    "which turns out to be O(2^length) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The above solution is purely recursive. We should be able to improve it by storing the results of the subproblems. Let me first consider a top-down approach. There are a lot of repeated subtrees, which means we could label the pos we have already checked by True and False directly. That will take O(length) space."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 165,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def canJump(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if nums==[]:\n",
    "            return True\n",
    "        # assign the root\n",
    "        n=len(nums)\n",
    "        r=[None]*len(nums)\n",
    "        return self.canJumpAux(nums,0,n,r)\n",
    "    \n",
    "    def canJumpAux(self,nums,pos,n,r):\n",
    "        if r[pos]!=None:\n",
    "            return r[pos]\n",
    "        # assign the root\n",
    "        root=nums[pos]\n",
    "        # if the maximum jump reaches the end, return true\n",
    "        if pos+nums[pos]>=n-1:\n",
    "            return True\n",
    "        # search children\n",
    "        for i in range(pos+1,pos+nums[pos]+1):\n",
    "            if self.canJumpAux(nums,i,n,r):\n",
    "                return True\n",
    "        \n",
    "        # label pos as False\n",
    "        r[pos]=False\n",
    "        \n",
    "        return r[pos]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 174,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 174,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.canJump([2,3,1,1,4])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Then we consider bottom-up solution. At any position that the jump starts, it can only jump to the right. So we could first label the last index as true, then we go backwards to the left of the list to check whether the nums[i] covers any element that is true. Once we reach the start of the list, we just return r[0]."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 172,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def canJump(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        n=len(nums)\n",
    "        r=[False]*n\n",
    "        r[n-1]=True\n",
    "        for i in range(n-2,-1,-1):\n",
    "            for j in range(i+1,i+nums[i]+1):\n",
    "                if r[j]==True:\n",
    "                    r[i]=True\n",
    "                    \n",
    "        return r[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 175,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 175,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.canJump([2,3,1,1,4])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The runtime is O(n^2) and the space is O(n). Can we do better in a Greedy algorithm? We always make the biggest 'backjump' from the last good position"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 254,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def canJump(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        n=len(nums)\n",
    "        last_good=n-1\n",
    "        for i in range(n)[::-1]:\n",
    "            if i+nums[i]>=last_good:\n",
    "                last_good=i\n",
    "        return last_good==0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 256,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 256,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.canJump([3,2,1,0,4])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 122. Best Time to Buy and Sell Stock II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Say you have an array for which the ith element is the price of a given stock on day i.\n",
    "\n",
    "Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: We need to capture all the increasing trend in the array."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 290,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def maxProfit(self, prices):\n",
    "        \"\"\"\n",
    "        :type prices: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        buy_time=0\n",
    "        sell_time=0\n",
    "        # track if last transaction is closed\n",
    "        complete=True\n",
    "        n=len(prices)\n",
    "        profit=0\n",
    "        for i in range(0,n):\n",
    "            if i==0 and i<n-1 and prices[i]<=prices[i+1]:\n",
    "                buy_time=i\n",
    "                complete=False\n",
    "            elif i==n-1 and not complete:\n",
    "                sell_time=i\n",
    "                profit+=prices[sell_time]-prices[buy_time]\n",
    "            elif i>0 and i<n-1:\n",
    "                if prices[i-1]>=prices[i] and prices[i]<=prices[i+1] and complete:\n",
    "                    buy_time=i\n",
    "                    complete=False\n",
    "                if prices[i-1]<=prices[i] and prices[i]>=prices[i+1] and not complete:\n",
    "                    sell_time=i\n",
    "                    profit+=prices[sell_time]-prices[buy_time]\n",
    "                    complete=True\n",
    "        return profit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 296,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 296,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "prices=[1,2,1,1]\n",
    "o.maxProfit(prices)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The above code can be improved as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 301,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def maxProfit(self, prices):\n",
    "        \"\"\"\n",
    "        :type prices: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n=len(prices)\n",
    "        profit=0\n",
    "        # edge case\n",
    "        if n<=1:\n",
    "            return profit\n",
    "        buy_time=0\n",
    "        sell_time=0\n",
    "        # track if last transaction is closed\n",
    "        if prices[0]<=prices[1]:\n",
    "            complete=False\n",
    "        else:\n",
    "            complete=True\n",
    "        for i in range(1,n-1):\n",
    "            if prices[i-1]>=prices[i] and prices[i]<=prices[i+1] and complete:\n",
    "                buy_time=i\n",
    "                complete=False\n",
    "            if prices[i-1]<=prices[i] and prices[i]>=prices[i+1] and not complete:\n",
    "                sell_time=i\n",
    "                profit+=prices[sell_time]-prices[buy_time]\n",
    "                complete=True\n",
    "        # complete any unclosed deal\n",
    "        if not complete:\n",
    "            sell_time=n-1\n",
    "            profit+=prices[sell_time]-prices[buy_time]\n",
    "        return profit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 302,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 302,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "prices=[1]\n",
    "o.maxProfit(prices)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There turns out to be a single pass solution as we only need to add up profit[i+1]>profit[i]."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 134. Gas Station"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There are N gas stations along a circular route, where the amount of gas at station i is gas[i].\n",
    "\n",
    "You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.\n",
    "\n",
    "Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.\n",
    "\n",
    "Note:\n",
    "The solution is guaranteed to be unique."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: Suppose the car starts at 0, if it finishes the circle, then\n",
    "\n",
    "gas[0]-cost[0]>0\n",
    "\n",
    "gas[0]-cost[0]+gas[1]-cost[1]>0\n",
    "\n",
    "...\n",
    "\n",
    "gas[0]-cost[0]+gas[1]-cost[1]+...gas[n]-cost[n]>0\n",
    "\n",
    "We could examine the net gain of gas for each link. The job can be done in a single pass: we start at 0, if \n",
    "\n",
    "gas[0]-cost[0]+gas[1]-cost[1]+...gas[i]-cost[i]<0 for some i\n",
    "\n",
    "then start=i+1 and if the remaining gain from i+1 to n can compensate for the loss, then we return the starting position."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 306,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def canCompleteCircuit(self, gas, cost):\n",
    "        \"\"\"\n",
    "        :type gas: List[int]\n",
    "        :type cost: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n=len(gas)\n",
    "        gain=[gas[i]-cost[i] for i in range(n)]\n",
    "        start=0\n",
    "        tank=0\n",
    "        compensate=0\n",
    "        for i in range(n):\n",
    "            if tank+gain[i]<0:\n",
    "                start=i+1\n",
    "                compensate+=tank+gain[i]\n",
    "                tank=0\n",
    "            else:\n",
    "                tank+=gain[i]\n",
    "        return start if tank+compensate>=0 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 309,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 309,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.canCompleteCircuit([5,3],[4,1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 455. Assign Cookies"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie. Each child i has a greed factor $g_i$, which is the minimum size of a cookie that the child will be content with; and each cookie j has a size $s_j$. If $s_j \\geq g_i$, we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number.\n",
    "\n",
    "Note:\n",
    "\n",
    "You may assume the greed factor is always positive.\n",
    "\n",
    "You cannot assign more than one cookie to one child.\n",
    "\n",
    "Example 1:\n",
    "\n",
    "Input: [1,2,3], [1,1]\n",
    "\n",
    "Output: 1\n",
    "\n",
    "Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3. \n",
    "And even though you have 2 cookies, since their size is both 1, you could only make the child whose greed factor is 1 content.\n",
    "You need to output 1.\n",
    "\n",
    "Example 2:\n",
    "\n",
    "Input: [1,2], [1,2,3]\n",
    "\n",
    "Output: 2\n",
    "\n",
    "Explanation: You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2. \n",
    "You have 3 cookies and their sizes are big enough to gratify all of the children, \n",
    "You need to output 2.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: Discussion solution: sort both lists; assign cookies from the least greedy child. Why does this work? If for the first child, $g_1>s_1$, then we have to move on to the cookie that could satisfy the first child; The same applies to the second child. Why is this the best case? Because if the cookies are assigned to anyone with high greediness, it can be assigned to the ones with low greediness without decreasing the total number of content children. Similarly, if one child is assigned with a large size satisfying his greediness, he could also be assigned with a smaller size cookie without decreasing the total number of content children."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def findContentChildren(self, g, s):\n",
    "        \"\"\"\n",
    "        :type g: List[int]\n",
    "        :type s: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # sort lists\n",
    "        g.sort()\n",
    "        s.sort()\n",
    "        # assign cookies to children\n",
    "        i=0\n",
    "        j=0\n",
    "        content_number=0\n",
    "        while i<len(g) and j<len(s):\n",
    "            if s[j]>=g[i]:\n",
    "                content_number+=1\n",
    "                i+=1\n",
    "                j+=1\n",
    "            else: # not satsifying the child, move on to the next larger size cookie\n",
    "                j+=1\n",
    "                \n",
    "        return content_number"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 452. Minimum Number of Arrows to Burst Balloons"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There are a number of spherical balloons spread in two-dimensional space. For each balloon, provided input is the start and end coordinates of the horizontal diameter. Since it's horizontal, y-coordinates don't matter and hence the x-coordinates of start and end of the diameter suffice. Start is always smaller than end. There will be at most 104 balloons.\n",
    "\n",
    "An arrow can be shot up exactly vertically from different points along the x-axis. A balloon with xstart and xend bursts by an arrow shot at x if xstart ≤ x ≤ xend. There is no limit to the number of arrows that can be shot. An arrow once shot keeps travelling up infinitely. The problem is to find the minimum number of arrows that must be shot to burst all balloons.\n",
    "\n",
    "Example:\n",
    "\n",
    "Input:\n",
    "[[10,16], [2,8], [1,6], [7,12]]\n",
    "\n",
    "Output:\n",
    "2\n",
    "\n",
    "Explanation:\n",
    "One way is to shoot one arrow for example at x = 6 (bursting the balloons [2,8] and [1,6]) and another arrow at x = 11 (bursting the other two balloons).\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: A greedy algorithm is to make every shot as effective as possible. We can first sort the list according to start time. Then we find the region for the first shoot. Remove the balloons bursts and then find the region for the second shoot...until all burst."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 194,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def findMinArrowShots(self, points):\n",
    "        \"\"\"\n",
    "        :type points: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if points==[]:\n",
    "            return 0\n",
    "        # sort the points\n",
    "        points.sort()\n",
    "        mark=points[0]\n",
    "        count=1\n",
    "        for i in range(1,len(points)):\n",
    "            if points[i][0]>mark[1]:\n",
    "                count+=1\n",
    "                mark=points[i]\n",
    "            else:\n",
    "                mark[1]=min(points[i][1],mark[1])\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 195,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 195,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.findMinArrowShots([[1,10],[2,3],[3,5],[6,7]])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 406. Queue Reconstruction by Height"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. Write an algorithm to reconstruct the queue.\n",
    "\n",
    "Note:\n",
    "The number of people is less than 1,100.\n",
    "\n",
    "Example\n",
    "\n",
    "Input:\n",
    "[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]\n",
    "\n",
    "Output:\n",
    "[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: Discussion solution: \n",
    "\n",
    "1. Sort first by height in descending order, then by index in ascending order. \n",
    "2. Insert elements in the second tallest group from left to right into the first tallest group according to their index. (As there will be no taller elements afterwards.)\n",
    "3. Repeat the procedure for 3rd, 4th ... tallest group.\n",
    "\n",
    "To realize the above algorithm we create a hashtable with height as key and lists of indices as values."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 226,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def reconstructQueue(self, people):\n",
    "        \"\"\"\n",
    "        :type people: List[List[int]]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        height_dict={}\n",
    "        for e in people:\n",
    "            if height_dict.get(e[0]):\n",
    "                height_dict[e[0]].append(e[1])\n",
    "            else:\n",
    "                height_dict[e[0]]=[e[1]]\n",
    "        heights=sorted(height_dict.keys(),reverse=True)\n",
    "        result=[]\n",
    "        for i in range(len(heights)):\n",
    "            if i==0:\n",
    "                height_dict[heights[i]].sort()\n",
    "                result+=[[heights[i],key] for key in height_dict[heights[i]]]\n",
    "            else:\n",
    "                height_dict[heights[i]].sort()\n",
    "                for pos in height_dict[heights[i]]:\n",
    "                    result.insert(pos,[heights[i],pos])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 227,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[5, 0], [7, 0], [5, 2], [6, 1], [4, 4], [7, 1]]"
      ]
     },
     "execution_count": 227,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "people=[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]\n",
    "o.reconstructQueue(people)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 402. Remove K Digits"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.\n",
    "\n",
    "Note:\n",
    "The length of num is less than 10002 and will be ≥ k.\n",
    "The given num does not contain any leading zero.\n",
    "\n",
    "Example 1:\n",
    "\n",
    "Input: num = \"1432219\", k = 3\n",
    "Output: \"1219\"\n",
    "Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.\n",
    "\n",
    "Example 2:\n",
    "\n",
    "Input: num = \"10200\", k = 1\n",
    "Output: \"200\"\n",
    "Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.\n",
    "\n",
    "Example 3:\n",
    "\n",
    "Input: num = \"10\", k = 2\n",
    "Output: \"0\"\n",
    "Explanation: Remove all the digits from the number and it is left with nothing which is 0.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: Given k=1, what should be removed first? We should remove the largest digit, but if the highest digit is followed with bunch of zeros, we should count them as one. For k>2, we remove the largest digit by the same method in the remaining number."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def removeKdigits(self, num, k):\n",
    "        \"\"\"\n",
    "        :type num: str\n",
    "        :type k: int\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<font color=red>\n",
    "The above idea is wrong take the example: 13425 for k=1, we have to remove 4 instead of 5. The right consideration is as follows: for s[i],i=0,1,2,... in num\n",
    "\n",
    "* if $s[i]<s[i+1]$: pass as remove s[i] will be larger than remove s[i+1]; if $s[i]>=s[i+1]$: remove s[i]. Notice that for k>=1, we need to move to the previous position such that all the k digits can be removed in one pass.\n",
    "\n",
    "\n",
    "* but if there is more to be removed, we just remove the remaining digits from the end. As the remaining digits in the number are strictly in ascending order.\n",
    "\n",
    "* Lastly, we need to take care of the leading zeros."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 252,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def removeKdigits(self, num, k):\n",
    "        \"\"\"\n",
    "        :type num: str\n",
    "        :type k: int\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        n=len(num)\n",
    "        i=0\n",
    "        t=0\n",
    "        num=list(num)\n",
    "        result=[]\n",
    "        while i<n:\n",
    "            result.append(num[i])\n",
    "            while t-1>=0 and result[t-1]>result[t] and k>0:\n",
    "                result.pop(t-1)\n",
    "                k-=1\n",
    "                t-=1\n",
    "            i+=1\n",
    "            t+=1\n",
    "        # check if there is more to be removed from the end\n",
    "        for i in range(k):\n",
    "            result.pop()\n",
    "        #check starting zeros\n",
    "        n=len(result)\n",
    "        start=0\n",
    "        while start<=n-1 and result[start]=='0':\n",
    "            start+=1\n",
    "            \n",
    "        return '0' if start>n-1 else ''.join(result[start:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 253,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'0'"
      ]
     },
     "execution_count": 253,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.removeKdigits('101',2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice that the corner case where all digits have been removed should be considered and the output is '0'."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## 435. Non-overlapping Intervals"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.\n",
    "\n",
    "Note:\n",
    "* You may assume the interval's end point is always bigger than its start point.\n",
    "* Intervals like [1,2] and [2,3] have borders \"touching\" but they don't overlap each other.\n",
    "\n",
    "Example 1:\n",
    "Input: [ [1,2], [2,3], [3,4], [1,3] ]\n",
    "\n",
    "Output: 1\n",
    "\n",
    "Explanation: [1,3] can be removed and the rest of intervals are non-overlapping.\n",
    "\n",
    "Example 2:\n",
    "Input: [ [1,2], [1,2], [1,2] ]\n",
    "\n",
    "Output: 2\n",
    "\n",
    "Explanation: You need to remove two [1,2] to make the rest of intervals non-overlapping.\n",
    "\n",
    "Example 3:\n",
    "Input: [ [1,2], [2,3] ]\n",
    "\n",
    "Output: 0\n",
    "\n",
    "Explanation: You don't need to remove any of the intervals since they're already non-overlapping.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: Intuitively, we will first remove the one that has the most number of overlaps with others, then the second most overlap interval...Specifically,\n",
    "\n",
    "1. sort the start of intervals: O(n log n)\n",
    "2. check if two intervals are overlapping: Brutal force: O(n^2), make a hashtable to record the overlapping intervals for each interval.\n",
    "3. remove the one with the largest list and then move on to the second largest...\n",
    "\n",
    "The above algorithm is not a good greedy algorithm. Instead, after sorting the intervals according to the starting point, we could remove the one with larger end in the overlapping pair of intervals as it is more likely to overlap the intervals afterwards."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Definition for an interval.\n",
    "class Interval(object):\n",
    "    def __init__(self, s=0, e=0):\n",
    "        self.start = s\n",
    "        self.end = e\n",
    "\n",
    "class Solution(object):\n",
    "    def eraseOverlapIntervals(self, intervals):\n",
    "        \"\"\"\n",
    "        :type intervals: List[Interval]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        intervals.sort(key=lambda x: x.start)\n",
    "        n=len(intervals)\n",
    "        if n==0: return 0\n",
    "        prev_end=intervals[0].end\n",
    "        count=0\n",
    "        for i in xrange(1,n):\n",
    "            if prev_end>intervals[i].start: # overlapping\n",
    "                count+=1\n",
    "                prev_end=min(prev_end,intervals[i].end)\n",
    "            else: # non-overlapping\n",
    "                prev_end=intervals[i].end\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "interval1=Interval()\n",
    "interval1.start=1\n",
    "interval1.end=2\n",
    "interval2=Interval()\n",
    "interval2.start=2\n",
    "interval2.end=3\n",
    "intervals=[interval1,interval2]\n",
    "o.eraseOverlapIntervals(intervals)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}