05_03_BinarySearchIII.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "run_control": {
     "frozen": false,
     "read_only": false
    }
   },
   "source": [
    "# Binary Search III"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "In this lecture, you will learn:\n",
    "\n",
    "<a href='#Ex1'>Ex.1 Merge Intervals</a>\n",
    "\n",
    "<a href='#Ex2'>Ex.2 Insert Intervals</a>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Interval:\n",
    "    def __init__(self, s=0, e=0):\n",
    "        self.start = s\n",
    "        self.end = e\n",
    "    \n",
    "    def __str__(self):\n",
    "        return \"[\" + self.start + \",\" + self.end + \"]\"\n",
    "    \n",
    "    def __repr__(self):\n",
    "        return \"[%s, %s]\" % (self.start, self.end)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "run_control": {
     "frozen": false,
     "read_only": false
    }
   },
   "source": [
    "### Ex.1: Merge Intervals\n",
    "\n",
    "Given a collection of intervals, merge all overlapping intervals.\n",
    "\n",
    "<img src=\"../images/ch05/mergeinterval.png\" width=\"580\"/>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def merge(intervals):\n",
    "    intervals.sort(key=lambda x: x.start)\n",
    "\n",
    "    merged = []\n",
    "    for interval in intervals:\n",
    "        # if the list of merged intervals is empty or if the current\n",
    "        # interval does not overlap with the previous, simply append it.\n",
    "        if not merged or merged[-1].end < interval.start:\n",
    "            merged.append(interval)\n",
    "        else:\n",
    "        # otherwise, there is overlap, so we merge the current and previous\n",
    "        # intervals.\n",
    "            merged[-1].end = max(merged[-1].end, interval.end)\n",
    "\n",
    "    return merged"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[1, 6], [8, 10], [15, 18]]\n"
     ]
    }
   ],
   "source": [
    "i1 = Interval(1,3)\n",
    "i2 = Interval(2,6)\n",
    "i3 = Interval(8,10)\n",
    "i4 = Interval(15,18)\n",
    "intervals = [i1,i2,i3,i4]\n",
    "print(merge(intervals))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[1, 6]]\n"
     ]
    }
   ],
   "source": [
    "i1 = Interval(1,4)\n",
    "i2 = Interval(4,6)\n",
    "intervals = [i1,i2]\n",
    "print(merge(intervals))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[0, 9], [10, 11], [12, 20]]\n",
      "[[0, 9], [0, 1], [0, 2], [1, 9], [2, 5], [10, 11], [12, 20], [19, 20]]\n"
     ]
    }
   ],
   "source": [
    "i1 = Interval(1,9)\n",
    "i2 = Interval(2,5)\n",
    "i3 = Interval(19,20)\n",
    "i4 = Interval(10,11)\n",
    "i5 = Interval(12,20)\n",
    "i6 = Interval(0,3)\n",
    "i7 = Interval(0,1)\n",
    "i8 = Interval(0,2)\n",
    "intervals = [i1,i2,i3,i4,i5,i6,i7,i8]\n",
    "print(merge(intervals))\n",
    "\n",
    "intervals.sort(key=lambda x: x.start)\n",
    "print(intervals)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Ex.2: Insert Intervals\n",
    "    \n",
    "Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).\n",
    "\n",
    "You may assume that the intervals were initially sorted according to their start times.\n",
    "\n",
    "<img src=\"../images/ch05/insertinterval.png\" width=\"580\"/>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def insert(intervals, newInterval):\n",
    "    merged = []\n",
    "    for i in intervals:\n",
    "        if newInterval is None or i.end < newInterval.start:\n",
    "            merged += i,\n",
    "        elif i.start > newInterval.end:\n",
    "            merged += newInterval,\n",
    "            merged += i,\n",
    "            newInterval = None\n",
    "        else:\n",
    "            newInterval.start = min(newInterval.start, i.start)\n",
    "            newInterval.end = max(newInterval.end, i.end)\n",
    "    if newInterval is not None:\n",
    "        merged += newInterval,\n",
    "    return merged"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1, 5], [6, 9]]"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "i1 = Interval(1,3)\n",
    "i2 = Interval(6,9)\n",
    "intervals = [i1,i2]\n",
    "new = Interval(2,5)\n",
    "insert(intervals, new)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1, 2], [3, 10], [12, 16]]"
      ]
     },
     "execution_count": 55,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "i1 = Interval(1,2)\n",
    "i2 = Interval(3,5)\n",
    "i3 = Interval(6,7)\n",
    "i4 = Interval(8,10)\n",
    "i5 = Interval(12,16)\n",
    "intervals = [i1,i2,i3,i4,i5]\n",
    "new = Interval(4,8)\n",
    "insert(intervals, new)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def insert2(intervals, newInterval):\n",
    "    left, right = [], []\n",
    "    for i in intervals:\n",
    "        if i.end < newInterval.start:\n",
    "            left += i,\n",
    "        elif i.start > newInterval.end:\n",
    "            right += i,\n",
    "        else:\n",
    "            newInterval.start = min(newInterval.start, i.start)\n",
    "            newInterval.end = max(newInterval.end, i.end)\n",
    "    return left + [Interval(newInterval.start, newInterval.end)] + right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1, 2], [3, 10], [12, 16]]"
      ]
     },
     "execution_count": 61,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "i1 = Interval(1,2)\n",
    "i2 = Interval(3,5)\n",
    "i3 = Interval(6,7)\n",
    "i4 = Interval(8,10)\n",
    "i5 = Interval(12,16)\n",
    "intervals = [i1,i2,i3,i4,i5]\n",
    "new = Interval(4,8)\n",
    "insert2(intervals, new)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def insert3(intervals, newInterval):\n",
    "    if len(intervals) == 0:\n",
    "        intervals += newInterval,\n",
    "    \n",
    "    startPos = searchPosition(intervals, newInterval.start)\n",
    "    endPos = searchPosition(intervals, newInterval.end)\n",
    "    \n",
    "    newStart = 0\n",
    "\n",
    "    # case 1:\n",
    "    # startPos\n",
    "    #           A\n",
    "    # |____|    |____|    |____|\n",
    "    #         <-  \n",
    "    #           startPos is less than A \n",
    "    # and intervals[startPos].end >= newInterval.start\n",
    "    # then \n",
    "    #   new     A\n",
    "    # |____|    |____|    |____|\n",
    "    #     <-  \n",
    "    # newInterval starts within ONE interval\n",
    "    # so newStart = intervals[startPos].start\n",
    "    if (startPos >= 0 and intervals[startPos].end >= newInterval.start):\n",
    "        newStart = intervals[startPos].start\n",
    "    else:\n",
    "        # case 2:\n",
    "        # startPos = -1\n",
    "        # A          \n",
    "        # |____|    |____|    |____|\n",
    "        # newInterval starts before 1st interval\n",
    "        # so newStart = newInterval.start\n",
    "\n",
    "        # case 3:\n",
    "        # startPos >= 0\n",
    "        # A    B          \n",
    "        # |____|    |____|    |____|\n",
    "        # newInterval starts between A and B\n",
    "        # so NOT intervals[startPos].end >= newInterval.start\n",
    "        # so newStart = newInterval.start         \n",
    "        newStart = newInterval.start\n",
    "        startPos += 1\n",
    "        \n",
    "    newEnd = 0\n",
    "    # case 1:\n",
    "    # endPos >= 0\n",
    "    # endPos\n",
    "    #           A\n",
    "    # |____|    |____|    |____|\n",
    "    #         <-  \n",
    "    #           endPos is less than A\n",
    "    # so newEnd = Math.max(newInterval.end, intervals.get(endPos).end)    \n",
    "    if (endPos >= 0):\n",
    "        newEnd = max(newInterval.end, intervals[endPos].end)\n",
    "    else:\n",
    "        # case 2:\n",
    "        # endPos < 0\n",
    "        # endPos\n",
    "        # A         \n",
    "        #     |____|    |____|    |____|\n",
    "        #            \n",
    "        # endPos is before 1st interval\n",
    "        # create a new interval        \n",
    "        newEnd = newInterval.end\n",
    "        \n",
    "    for i in range(startPos, endPos+1):\n",
    "        intervals.pop(startPos)  # note: NOT i, but startPos, since one element is removed.\n",
    "\n",
    "    intervals.insert(startPos, Interval(newStart, newEnd))\n",
    "    return intervals\n",
    "\n",
    "# return (actual insertion position - 1)\n",
    "def searchPosition(intervals, x):\n",
    "    start = 0\n",
    "    end = len(intervals) - 1\n",
    "    while (start <= end):\n",
    "        mid = start + (end - start) // 2\n",
    "        if (intervals[mid].start == x):\n",
    "            return mid\n",
    "        if (intervals[mid].start < x):\n",
    "            start = mid + 1\n",
    "        else:\n",
    "            end = mid - 1\n",
    "\n",
    "    return end\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1, 2], [3, 10], [12, 16]]"
      ]
     },
     "execution_count": 71,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "i1 = Interval(1,2)\n",
    "i2 = Interval(3,5)\n",
    "i3 = Interval(6,7)\n",
    "i4 = Interval(8,10)\n",
    "i5 = Interval(12,16)\n",
    "intervals = [i1,i2,i3,i4,i5]\n",
    "new = Interval(4,8)\n",
    "insert3(intervals, new)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "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.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}