Intervals.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "c379a5b5",
   "metadata": {},
   "source": [
    "# Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5bfb5f52",
   "metadata": {},
   "source": [
    "## Meeting Rooms\n",
    "\n",
    "* https://www.lintcode.com/problem/920/\n",
    "***\n",
    "* Time Complexity: O(nlogn)\n",
    "    - must sort intervals arr by start time: O(nlogn)\n",
    "    - then traverse through intervals arr and find any overlaps O(n)\n",
    "* Space Complexity: O(1)\n",
    "    - only needs space for a couple of variables\n",
    "***\n",
    "* we sort intervals by start time so that it is easier to traverse the arr and determine if there is an overlap\n",
    "    - we just see if int1[end] > int2[start]\n",
    "    - if it is, we return false"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "1c72f1a4",
   "metadata": {},
   "outputs": [],
   "source": [
    "/**\n",
    " * Definition of Interval:\n",
    " * class Interval {\n",
    " *   constructor(start, end) {\n",
    " *     this.start = start;\n",
    " *     this.end = end;\n",
    " *   }\n",
    " * }\n",
    " */\n",
    "\n",
    "var Solution = class {\n",
    "  /**\n",
    "   * @param intervals: an array of meeting time intervals\n",
    "   * @return: if a person could attend all meetings\n",
    "   */\n",
    "  canAttendMeetings(intervals) {\n",
    "    const n = intervals.length;\n",
    "\n",
    "    if (n === 1) return true;\n",
    "\n",
    "    // sort it by start times\n",
    "    intervals.sort((a, b) => a.start - b.start);\n",
    "\n",
    "    let newInterval = intervals[0];\n",
    "    for (let i = 1; i < n; i++) {\n",
    "      if (newInterval.end > intervals[i].start) {\n",
    "        return false;\n",
    "      }\n",
    "\n",
    "      newInterval = intervals[i];\n",
    "    }\n",
    "\n",
    "    return true;\n",
    "  }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e59a494c",
   "metadata": {},
   "source": [
    "# Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "95fae4cf",
   "metadata": {},
   "source": [
    "## Insert Interval\n",
    "\n",
    "* https://leetcode.com/problems/insert-interval/description/\n",
    "***\n",
    "* Time Complexity: O(n)\n",
    "    - only needs to traverse through the array once\n",
    "* Space Complexity: O(n)\n",
    "    - requires space for the res array\n",
    "***\n",
    "* identify all non-mergeable intervals as you traverse and push them into the res array\n",
    "    - so if I[end] < newInterval[start], then push\n",
    "* once you've identified your first mergeable interval, you do the merge operation on the newInterval itself\n",
    "    - newInterval is used as the accumulator so that you don't have to constantly keep track of it at the end of the res arr\n",
    "    - once all of them have been merged, you then push newInterval onto the res array\n",
    "    - there's also the case where none of them can be merged but you haven't reached the end of the arr\n",
    "        * in that case, you just push the newInterval without doing any merge operations\n",
    "        * e.g. intervals = [[1,2], [12, 15]], newIntervals = [6,6]\n",
    "            - the first while loop condition breaks at [12,15] but it cannot be merged with [6,6]\n",
    "            - thus you would just push newInterval into res and then the rest of it\n",
    "            - so res = [[1,2], [6,6], [12,15]]\n",
    "* once all the intervals have been merged, then you add the rest of intervals into res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "50e2d75a",
   "metadata": {},
   "outputs": [],
   "source": [
    "/**\n",
    " * @param {number[][]} intervals\n",
    " * @param {number[]} newInterval\n",
    " * @return {number[][]}\n",
    " */\n",
    "\n",
    "// O(1)\n",
    " const canMerge = (interval, newInterval) => {\n",
    "   const start = 0;\n",
    "   const end = 1;\n",
    "   return (newInterval[end] >= interval[start] && newInterval[end] <= interval[end]) ||\n",
    "          (newInterval[start] >= interval[start] && newInterval[start] <= interval[end]) ||\n",
    "          (newInterval[start] <= interval[start] && newInterval[end] >= interval[end]);\n",
    " }\n",
    "\n",
    "// O(1)\n",
    " const merge = (arr1, arr2) => {\n",
    "   const start = Math.min(arr1[0], arr2[0]);\n",
    "   const end = Math.max(arr1[1], arr2[1]);\n",
    "   return [start, end];\n",
    " }\n",
    "\n",
    "// Time Complexity: O(n)\n",
    "// Space Complexity: O(n)\n",
    "var insert = function(intervals, newInterval) {\n",
    "  // case 0: intervals = [], newInterval = [1,2]\n",
    "  // return [[1,2]]\n",
    "  if (intervals.length === 0) return [newInterval];\n",
    "\n",
    "  // case 1: intervals = [3,5], newInterval = [1,2]\n",
    "  // return [[1,2], [3,5]]\n",
    "  if (newInterval[1] < intervals[0][0]) {\n",
    "    return [newInterval, ...intervals];\n",
    "  }\n",
    "\n",
    "  // 1) if nI[end] < I[start], push nI and set flag to indicate do not merge again\n",
    "  // 2) if canMerge, then merge and set newInterval as the recently merged\n",
    "  // 3) if can't merge it, just push it\n",
    "\n",
    "  const res = [];\n",
    "  let pushed = false;\n",
    "  let merged = false;\n",
    "  for (let i = 0; i < intervals.length; i++) {\n",
    "    if (canMerge(intervals[i], newInterval)) {\n",
    "      const newArr = merged ? merge(intervals[i], res.pop()) : merge(intervals[i], newInterval);\n",
    "      res.push(newArr);\n",
    "      merged = true;\n",
    "      continue;\n",
    "    }\n",
    "    else if (!pushed && !merged && (newInterval[1] < intervals[i][0])) {\n",
    "      res.push(newInterval);\n",
    "      pushed = true;\n",
    "    }\n",
    "\n",
    "    res.push(intervals[i]);\n",
    "  }\n",
    "\n",
    "  // case 2: intervals = [1,2], newInterval = [3,5]\n",
    "  // return [[1,2], [3,5]]\n",
    "  if (!merged && !pushed) {\n",
    "    res.push(newInterval);\n",
    "  }\n",
    "\n",
    "  return res;\n",
    "}\n",
    "\n",
    "// cleaner solution\n",
    "var insert = function(intervals, newInterval) {\n",
    "    const n = intervals.length;\n",
    "    const res = [];\n",
    "    let i = 0;\n",
    "\n",
    "    // case 0: keep going until you find a mergeable interval\n",
    "    // while I[end] < newI[start]\n",
    "    while (i < n && intervals[i][1] < newInterval[0]) {\n",
    "        res.push(intervals[i]);\n",
    "        i++;\n",
    "    }\n",
    "\n",
    "    // case 2: continue merging intervals until you can't anymore\n",
    "    // nI[end] >= I[start]\n",
    "    while (i < n && newInterval[1] >= intervals[i][0]) {\n",
    "        newInterval[0] = Math.min(newInterval[0], intervals[i][0]);\n",
    "        newInterval[1] = Math.max(newInterval[1], intervals[i][1]);\n",
    "        i++;\n",
    "    }\n",
    "\n",
    "    // this handles 2 cases:\n",
    "    // 1) if case 0 is true for all intervals, then you just add it to the end\n",
    "    // 2) if we have to insert newInterval half-way into the res w/o needing to merge\n",
    "    res.push(newInterval);\n",
    "\n",
    "    // case 3: no more intervals left to merge with\n",
    "    while (i < n) {\n",
    "        res.push(intervals[i]);\n",
    "        i++;\n",
    "    }\n",
    "\n",
    "    return res;\n",
    "\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2f905e1f",
   "metadata": {},
   "source": [
    "## Merge Intervals\n",
    "\n",
    "* https://leetcode.com/problems/merge-intervals/description/\n",
    "***\n",
    "* Time Complexity: O(nlogn)\n",
    "    - must sort the intervals arr: O(nlogn)\n",
    "    - must traverse intervals arr: O(n)\n",
    "        * not dominant term\n",
    "* Space Complexity: O(n)\n",
    "    - requires space for res array\n",
    "***\n",
    "* the intervals arr is not sorted by default\n",
    "* sorting helps tremendously b/c the alternative is that it would take O(n$^{2}$) time to compare one interval with other potential mergers\n",
    "    - instead, when you sort the intervals arr, you just compare interval1[end] and interval2[start]\n",
    "    - e.g. [[1,2][3,4]]\n",
    "        * is 2 >= 3? No, so you cannot merge them!\n",
    "    - and if you don't need to merge them, you just move on b/c you know that the rest of the intervals would also not be mergeable b/c their start is ALWAYS going to be smaller than the end of the previous intervals\n",
    "* once sorting is done, you set the first interval as the newInterval\n",
    "    - newInterval is used to keep track of previous intervals and/or intervals that already merged\n",
    "* as we traverse through intervals arr, we have 2 options:\n",
    "    - if we can merge with newInterval, we do not push the current interval into res\n",
    "    - else, we push newInterval into res and we reset newInterval to be equal to the current interval\n",
    "    - think of this like Kadane's algorithm a bit\n",
    "* we go from i...n inclusively\n",
    "    - this solves for the edge case where we arrive at the last interval and must push it\n",
    "    - if we do not include n, we will miss merging or pushing the last interval"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "a65c62d4",
   "metadata": {},
   "outputs": [],
   "source": [
    "/**\n",
    " * @param {number[][]} intervals\n",
    " * @return {number[][]}\n",
    " */\n",
    "var merge = function(intervals) {\n",
    "  const n = intervals.length;\n",
    "  if (n === 1) return intervals;\n",
    "\n",
    "  // O(nlogn)\n",
    "  // without sorting it, you'd have to check each interval with each other\n",
    "  // which would be O(n^2)\n",
    "  intervals.sort((a, b) => a[0] - b[0]);\n",
    "\n",
    "//   console.log({intervals});\n",
    "\n",
    "  /**\n",
    "    * set newInterval to be first interval by default\n",
    "    * then you have 2 options:\n",
    "        1. if the next interval can be merged with newInterval, then perform the merge operation\n",
    "        2. else, you push newInterval and set newInterval as current interval\n",
    "    * this allows you to keep track of previous intervals that you've seen and\n",
    "    * and since we do i <= n, we solve an edge case where we merge the last interval and allow it to\n",
    "      be pushed into the res array. without this, you'd be missing the last interval b/c you break out\n",
    "      of the loop before ever pushing it\n",
    "    */\n",
    "   const res = [];\n",
    "   let newInterval = intervals[0];\n",
    "   for (let i = 1; i <= n; i++) {\n",
    "       if (i < n && newInterval[1] >= intervals[i][0]) {\n",
    "        // actually don't need this b/c it's already sorted by start\n",
    "        // so if you keep traversing the arr while merging with newInterval,\n",
    "        // newInterval will always have the min start\n",
    "        //    newInterval[0] = Math.min(newInterval[0], intervals[i][0]);\n",
    "           newInterval[1] = Math.max(newInterval[1], intervals[i][1]);\n",
    "       }\n",
    "       else {\n",
    "           res.push(newInterval);\n",
    "           newInterval = intervals[i];\n",
    "       }\n",
    "   }\n",
    "\n",
    "//    console.log({res});\n",
    "   return res;\n",
    "};"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "76c99826",
   "metadata": {},
   "source": [
    "## Non-overlapping Intervals\n",
    "\n",
    "* https://leetcode.com/problems/non-overlapping-intervals/\n",
    "***\n",
    "* Time Complexity: O(nlogn)\n",
    "    - must sort the intervals: O(nlogn)\n",
    "    - must traverse intervals arr: O(n)\n",
    "        * non-dominant term\n",
    "* Space Complexity: O(1)\n",
    "    - only requires space for a couple of variables\n",
    "***\n",
    "* similar to the other interval questions\n",
    "* cannot assume that intervals arr is sorted so we sort by the start of the interval\n",
    "* then as we traverse the arr, we check if there is an overlap\n",
    "    - if there is, we increment the count\n",
    "    - then we merge the interval with new interval but with a twist\n",
    "        * instead of taking the max of the end of the intervals, we instead take the min\n",
    "        * we do this b/c we want to MINIMIZE the reach of the intervals so that there's less of a chance for it to overlap with other intervals\n",
    "        * e.g. [1,11], [2,12], [11,22]\n",
    "            - [1,11] and [2,12] overlap\n",
    "            - so we merge them and take the min which would be [1,11]\n",
    "            - we see that [1,11] DOES NOT overlap with [11,12] but if we were to take the max instead, we would get [1,12] which WOULD overlap"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "3d32dfb5",
   "metadata": {},
   "outputs": [],
   "source": [
    "/**\n",
    " * @param {number[][]} intervals\n",
    " * @return {number}\n",
    " */\n",
    "var eraseOverlapIntervals = function(intervals) {\n",
    "  const n = intervals.length;\n",
    "  if (n === 1) return 0;\n",
    "\n",
    "  intervals.sort((a, b) => a[0] - b[0]);\n",
    "\n",
    "  let minInts = 0;\n",
    "  let newInterval = intervals[0];\n",
    "  for (let i = 1; i < n; i++) {\n",
    "    if (newInterval[1] > intervals[i][0]) {\n",
    "      // you take the min so that it reduces the reach of your current interval\n",
    "      // so that there's less of a chance for overlap with other intervals\n",
    "      // e.g. [[1,11], [2,12], [11,22]]\n",
    "      // if newInterval = [1,11], then merging with [2,12] would get us [1,11]\n",
    "      // this minimizes our reach since [1,11] does not overlap with [11,22] but [2,12] does!\n",
    "      newInterval[1] = Math.min(newInterval[1], intervals[i][1]);\n",
    "      minInts++;\n",
    "    }\n",
    "    else {\n",
    "      newInterval = intervals[i];\n",
    "    }\n",
    "  }\n",
    "\n",
    "  return minInts;\n",
    "};"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "24c37b4d",
   "metadata": {},
   "source": [
    "## Meeting Rooms II\n",
    "\n",
    "* https://www.lintcode.com/problem/919/description\n",
    "***\n",
    "* Time Complexity: O(nlogn)\n",
    "    - traverse through all intervals and push the start/end times into an arr: O(n)\n",
    "    - sort the meetings arr: O(nlogn)\n",
    "        * the # of entries in the meetings arr is actually 2n b/c we push both start and end times separately\n",
    "* Space Complexity: O(n)\n",
    "    - needs space for the meetings arr\n",
    "***\n",
    "* similar to Kadane's algorithm\n",
    "* we traverse through the intervals arr and push the start times and end times for each interval separately\n",
    "    - [interval.start, 1] and [interval.end, -1]\n",
    "    - a start time indicates a meeting starting and an end time indicates a meeting ending\n",
    "    - so the 1 and -1 respectively will adjust the # of meetings going on at a time, which corresponds to the # of conference rooms\n",
    "* once we have filled up the meetings arr, we sort it\n",
    "    - we do this b/c we want to determine how many concurrent meetings, and therefore conference rooms being used, there are\n",
    "    - so if we have 2 start times in a row, that tells us that there are 2 meetings happening at the same time, which require 2 conference rooms\n",
    "    - however, if the next time is an end time, then we know that a meeting has ended and the # of meetings and conference rooms have gone down\n",
    "* as we traverse meetings, the # of meetings/conference rooms will reach a peak then go down to 0 b/c all meetings have ended by the time we have traversed the entire meetings arr\n",
    "    - therefore, we must take the max # of meetings after every loop to ensure we get our # of conference rooms"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "493fe650",
   "metadata": {},
   "outputs": [],
   "source": [
    "/**\n",
    " * Definition of Interval:\n",
    " * class Interval {\n",
    " *   constructor(start, end) {\n",
    " *     this.start = start;\n",
    " *     this.end = end;\n",
    " *   }\n",
    " * }\n",
    " */\n",
    "\n",
    "var Solution = class {\n",
    "  /**\n",
    "   * @param intervals: an array of meeting time intervals\n",
    "   * @return: the minimum number of conference rooms required\n",
    "   */\n",
    "  minMeetingRooms(intervals) {\n",
    "    const n = intervals.length;\n",
    "    if (n === 1) return 1;\n",
    "\n",
    "    // essentially, every time a meeting starts, we increment # of meetings by 1\n",
    "    // and every time a meeting ends, we decrement # of meetings by 1\n",
    "    // so we keep track of these in an arr\n",
    "    const meetings = [];\n",
    "    intervals.forEach(interval => {\n",
    "      meetings.push([interval.start, 1]);\n",
    "      meetings.push([interval.end, -1]);\n",
    "    })\n",
    "\n",
    "    // we then sort the meetings arr by their time\n",
    "    meetings.sort((a, b) => a[0] - b[0]);\n",
    "\n",
    "    // pretty similar to Kadane's algorithm\n",
    "    // we aren't looking for overlaps here!\n",
    "    // we know that a meeting HAS to start and it HAS to end\n",
    "    // if a meeting starts and then another meeting starts after it with the previous one not ending yet,\n",
    "    // then we'll need 2 conference rooms\n",
    "    // but if one of them ends, then we only have need for 1 conference room\n",
    "    \n",
    "    // the reason why we need to take the max every time is b/c by the end of all meetings, it'll be back to 0\n",
    "    // so we must look at the max concurrent meetings\n",
    "    let maxMeetings = 0;\n",
    "    let runningMeetings = 0;\n",
    "    for (let [_, delta] of meetings) {\n",
    "      runningMeetings += delta;\n",
    "      maxMeetings = Math.max(maxMeetings, runningMeetings);\n",
    "    }\n",
    "\n",
    "    return maxMeetings;\n",
    "  }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4bd16fdb",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "JavaScript (Node.js)",
   "language": "javascript",
   "name": "javascript"
  },
  "language_info": {
   "file_extension": ".js",
   "mimetype": "application/javascript",
   "name": "javascript",
   "version": "16.14.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}