05-18-20_interval_related.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 28. Implement strStr()\n",
    "\n",
    "\n",
    "Implement strStr().\n",
    "\n",
    "Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.\n",
    "\n",
    "Example 1:\n",
    "\n",
    "Input: haystack = \"hello\", needle = \"ll\"\n",
    "Output: 2\n",
    "Example 2:\n",
    "\n",
    "Input: haystack = \"aaaaa\", needle = \"bba\"\n",
    "Output: -1\n",
    "Clarification:\n",
    "\n",
    "What should we return when needle is an empty string? This is a great question to ask during an interview.\n",
    "\n",
    "For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C's strstr() and Java's indexOf()."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def strStr(self, haystack: str, needle: str) -> int:\n",
    "        n = len(needle)\n",
    "        index = -1\n",
    "        for i in range(len(haystack) - n + 1):\n",
    "            if haystack[i:i+ n] == needle:\n",
    "                index = i\n",
    "                break\n",
    "        return index"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 452. Minimum Number of Arrows to Burst Balloons\n",
    "\n",
    "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)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [],
   "source": [
    "# initial version: time limit exceeded\n",
    "\n",
    "class Solution:\n",
    "    def findMinArrowShots(self, points: List[List[int]]) -> int:\n",
    "     \n",
    "\n",
    "        n = len(points) \n",
    "\n",
    "        points.sort(key=lambda x: x[0])\n",
    "        \n",
    "        start = []\n",
    "        end = []\n",
    "        for i in range(n):\n",
    "            start.append(points[i][0])\n",
    "            end.append(points[i][1])\n",
    "        \n",
    "        num = 0\n",
    "        j = 0\n",
    "        while n >= j + 2:\n",
    "            flag = 0\n",
    "            for i in range(n-j, 1, -1):\n",
    "                r = min(end[j:j+i])\n",
    "                l = max(start[j:j+i])\n",
    "                if r >= l:\n",
    "                    flag = 1\n",
    "                    break\n",
    "            num += 1\n",
    "            if flag == 1:\n",
    "                j += i\n",
    "            else:\n",
    "                j += 1\n",
    "        if j < n:\n",
    "            num += 1\n",
    "        \n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [],
   "source": [
    "# other's solution:\n",
    "\n",
    "class Solution:\n",
    "    def findMinArrowShots(self, points: List[List[int]]) -> int:\n",
    "        points.sort(key=lambda x:x[1])\n",
    "        end = - float('inf')\n",
    "        cnt = 0\n",
    "        for p in points:\n",
    "            if p[0] <= end:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                end = p[1]\n",
    "        return len(points)-cnt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The logic is the same, there is no need to compare multiple subset of the startpoints and endpoints"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 435. Non-overlapping Intervals\n",
    "\n",
    "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",
    " \n",
    "\n",
    "Example 1:\n",
    "\n",
    "Input: [[1,2],[2,3],[3,4],[1,3]]\n",
    "Output: 1\n",
    "Explanation: [1,3] can be removed and the rest of intervals are non-overlapping.\n",
    "\n",
    "\n",
    "Example 2:\n",
    "\n",
    "Input: [[1,2],[1,2],[1,2]]\n",
    "Output: 2\n",
    "Explanation: You need to remove two [1,2] to make the rest of intervals non-overlapping.\n",
    "\n",
    "\n",
    "Example 3:\n",
    "\n",
    "Input: [[1,2],[2,3]]\n",
    "Output: 0\n",
    "Explanation: You don't need to remove any of the intervals since they're already non-overlapping."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        intervals.sort(key=lambda x:x[1])\n",
    "        end = - float('inf')\n",
    "        cnt = 0\n",
    "        for inter in intervals:\n",
    "            if inter[0] < end:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                end = inter[1]\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 56. Merge Intervals\n",
    "\n",
    "Given a collection of intervals, merge all overlapping intervals.\n",
    "\n",
    "Example 1:\n",
    "\n",
    "Input: [[1,3],[2,6],[8,10],[15,18]]\n",
    "Output: [[1,6],[8,10],[15,18]]\n",
    "Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].\n",
    "\n",
    "\n",
    "Example 2:\n",
    "\n",
    "Input: [[1,4],[4,5]]\n",
    "Output: [[1,5]]\n",
    "Explanation: Intervals [1,4] and [4,5] are considered overlapping.\n",
    "NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def merge(self, intervals: List[List[int]]) -> List[List[int]]:\n",
    "        if len(intervals) < 2:\n",
    "            return intervals\n",
    "        else:\n",
    "            intervals.sort(key=lambda x:x[0])\n",
    "\n",
    "            result = []\n",
    "            temptinterval = intervals[0]\n",
    "            for inter in intervals[1:]:\n",
    "                if inter[0] <= temptinterval[1]:\n",
    "                    temptinterval[0] = min(temptinterval[0], inter[0])\n",
    "                    temptinterval[1] = max(temptinterval[1], inter[1])\n",
    "                else:\n",
    "                    result.append(temptinterval)\n",
    "                    temptinterval = inter\n",
    "            result.append(temptinterval)\n",
    "            return result"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Interesting, when consider union, sort by the startpoints"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1288. Remove Covered Intervals\n",
    "\n",
    "Given a list of intervals, remove all intervals that are covered by another interval in the list. Interval [a,b) is covered by interval [c,d) if and only if c <= a and b <= d.\n",
    "\n",
    "After doing so, return the number of remaining intervals.\n",
    "\n",
    " \n",
    "\n",
    "Example 1:\n",
    "\n",
    "Input: intervals = [[1,4],[3,6],[2,8]]\n",
    "Output: 2\n",
    "Explanation: Interval [3,6] is covered by [2,8], therefore it is removed.\n",
    " \n",
    "\n",
    "Constraints:\n",
    "\n",
    "1 <= intervals.length <= 1000\n",
    "0 <= intervals[i][0] < intervals[i][1] <= 10^5\n",
    "intervals[i] != intervals[j] for all i != j"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Biggest problem for me is how to deal with duplicates\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        n = len(intervals) \n",
    "        if n < 2:\n",
    "            return n\n",
    "        \n",
    "        intervals = sorted(sorted(intervals, key = lambda x : x[0], \n",
    "                                  reverse = True), key = lambda x : x[1]) \n",
    "        \n",
    "        start = [x[0] for x in intervals]\n",
    "        \n",
    "        cnt = 0\n",
    "        for i in range(n-1):\n",
    "            if start[i] >= min(set(start[i+1:])):\n",
    "                cnt += 1\n",
    "        return len(intervals) - cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Other's solution, much faster\n",
    "\n",
    "class Solution:\n",
    "    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:\n",
    "        res, right_most = len(intervals), 0\n",
    "        for interval in sorted(intervals, key=lambda i: (i[0], -i[1])):\n",
    "            if interval[1] <= right_most:\n",
    "                res -= 1\n",
    "            right_most = max(right_most, interval[1])\n",
    "        return res"
   ]
  }
 ],
 "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.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}