Optimisation: Dynamic Programming and Greedy¶

Table of Contents

Dynamic Programming
Greedy

Dynamic Programming¶

Unique Paths

Expand Code

def uniquePaths(self, m: int, n: int) -> int:
  def grid():
    dp = [[0] * n for _ in range(m)]
    for i in range(m):
      dp[i][0] = 1
    for j in range(n):
      dp[0][j] = 1
    for i in range(1, m):
      for j in range(1, n):
        dp[i][j] = dp[i-1][j] + dp[i][j-1]
    return dp[-1][-1]
  
  def optimized():
    # f(i,j) = f(i-1,j) + f(i,j-1)
    # remove the first diemsion
    # f(j) = f(j) + f(j-1) <- as long as f(j-1) is from the current iteration
    # and f(j) is from the previous iteration
    # so we need to fill this from left to right
    dp = [1] * n
    for i in range(1, m):
      for j in range(1, n):
        dp[j] = dp[j] + dp[j-1]
    return dp[-1]
  
  return optimized()

def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
  # dp[i][j] = 0 if obstacle
  # dp[i][j] = dp[i-1][j] + dp[i][j-1]
  # we can remove first dimension as it only depends on i-1
  # dp[j] = dp[j] (from previous row) + dp[j-1] (current row)
  # we need to fill it from left to right
  # initialization: if there is an obstacle in the first row,
  # all other cells after that would be unreachable
  m, n = len(obstacleGrid), len(obstacleGrid[0]) if len(obstacleGrid) > 0 else 0
  dp = [0] * n
  j = 0
  while j < n and not obstacleGrid[0][j]:
    dp[j] = 1
    j += 1
  for i in range(1, m):
    # this step is very important
    # we not only need to check for obstacles in the current cell, but also previous cell
    dp[0] = 1 if not obstacleGrid[i][0] and dp[0] else 0
    for j in range(1, n):
      dp[j] = dp[j] + dp[j-1] if not obstacleGrid[i][j] else 0
  return dp[-1]

Longset Common Subsequence

Expand Code

def lcs():
  # say, we have sene i characters from text1 and j characters from text2
  # the lcs(i, j) contains the longest common subsequence.
  # if text1[i+1] == text2[j+1] then we increase lcs by 1
  # else lcs is the max of lcs(i, j), lcs(i+1, j) and lcs(i, j+1)
  # in the end, the final lcs is found at lcs(m, n)
  m, n = len(text1), len(text2)
  # dp table
  lcs = [[0] * (n+1) for _ in range(m+1)]
  # for every lcs(i+1, j+1), we need lcs(i, j), lcs(i+1, j) and lcs(i, j+1)
  # that is, previous row and previous column of the same row
  # so we have to fill the array from left to right, top to bottom
  for i in range(m):
    for j in range(n):
      if text1[i] == text2[j]:
        lcs[i+1][j+1] = lcs[i][j] + 1
      else:
        lcs[i+1][j+1] = max(lcs[i+1][j], lcs[i][j+1])

  return lcs[m][n]

def lcs_memory_optimized():
  # f(i,j) = length of lcs from s[0..i-1] and t[0...j-1]
  # transition rule:
  # f(i+1,j+1) = f(i,j) + 1 if s[i] = t[j]
  # f(i+1,j+1) = max(f(i+1,j), f(i,j+1))
  """ IMPORTANT THIS """
  # cannot be reduced to one dimension
  # f(j+1) = f(j) + 1 if s[i] == t[j] (need f(j) from previous iteration)
  # f(j+1) = f(j) (current iteration) + f(j+1) (previous iteration)
  # need to keep track of the previous row
  m, n = len(s), len(t)
  dp_prev, dp = [0] * (n + 1), [0] * (n + 1)
  for i in range(m):
    for j in range(n):
      if s[i] == t[j]:
        dp[j+1] = dp_prev[j] + 1
      else:
        dp[j+1] = max(dp[j], dp_prev[j+1])
    dp_prev = dp[:]
  return dp[-1]

def construct(stack, indicators, i, j):
  if i == 0 or j == 0:
    return
  if indicators[i][j] == 1:
    construct(stack, indicators, i-1, j-1)
    # need to keep this in mind that we only add characters in this case
    stack.append(text1[i-1])
  elif indicators[i][j] == 2:
    construct(stack, indicators, i-1, j)
  else:
    construct(stack, indicators, i, j-1)

def lcs_str() -> str:
  # need to keep additional storage for longest common subsequence string
  # just need to store an indicator:
  # 0 means it came from same row, previous column
  # 1 means it came from previous row, previous column
  # 2 means it came from previous row, same column
  # also need to keep track of the index??
  m, n = len(text1), len(text2)
  prev_row, curr_row = [0] * (n+1), [0] * (n+1)
  indicators = [[0] * (n+1) for _ in range(m+1)]

  for i in range(m):
    for j in range(n):
      if text1[i] == text2[j]:
        curr_row[j+1] = prev_row[j] + 1
        indicators[i+1][j+1] = 1
      else:
        if prev_row[j+1] < curr_row[j]:
          curr_row[j+1] = curr_row[j]
          indicators[i+1][j+1] = 0
        else:
          curr_row[j+1] = prev_row[j+1]
          indicators[i+1][j+1] = 2

    # copy current row to previous
    for k in range(len(curr_row)):
      prev_row[k] = curr_row[k]

  stack = []
  construct(stack, indicators, m, n)
  return ''.join(stack)

Longest Increasing Subsequence: [princeton.edu] Patience Sorting: Longest increasing subsequence

Expand Code

def use_patience_solitaire():
  # we take the numbers as cards and deal them one by one to create decks
  # (a) for a card, check the decks from left to right
  # (b) if the card is smaller than the card on that deck, it goes on top
  # (c) else we create a new deck with the card
  # Note:
  # (a) if we form the decks this way, the within a given deck, the numbers are
  #     arranged in decreasing order
  # (b) the top card of the decks would be in increasing order from left to right
  # (c) the number of decks created this way is the length of longest increasing subsequence
  decks = [nums[0]]
  for num in nums[1:]:
    if decks and decks[-1] < num:
      decks.append(num)
    else:
      insert_index = bisect_left(decks, num)
      decks[insert_index] = num
  return len(decks)

def use_dp():
  # lis[i] is the longest increasing subsequence ending at nums[i]
  # once I see nums[i+1], I need to consider all previous lis[k]
  # instances k <= i, where nums[k] < nums[i+1]. The new number is
  # able to create an lis of an increased length by 1
  # base case: every lis[i] is at least 1
  n = len(nums)
  dp = [1] * n
  max_len = 1
  for i in range(1, n):
    for k in range(i):
      if nums[k] < nums[i]:
        dp[i] = max(dp[i], dp[k] + 1)
        max_len = max(max_len, dp[i])
  return max_len

Longest Palindromic Subsequence

Expand Code

def longestPalindromeSubseq(self, s: str) -> int:
  def lps(s):
    # f(i,j) = length of lps after seeing s[i+1...j-1]
    # need to compute f(i-1,j+1) after seeing s[i] and s[j]
    # transition rule:
    # f(i-1,j+1) = f(i,j) + 2 if s[i] == s[j]
    # f(i-1,j+1) = max(f(i-1,j), f(i,j+1)) otherwise
    # normalized equations
    # f(i,j) = f(i+1,j-1) + 2 if s[i] == s[j]
    # f(i,j) = max(f(i,j-1), f(i+1,j)) otherwise
    # need to fill rows from bottom to top
    # cannot remove dimension i
    # when state (i,j) is updated, we need to know
    #   j-1 from next row
    #   j-1 from current row and j from next row
    # so we need to keep track of the previous row
    n = len(s)
    dp_prev, dp = [0] * n, [0] * n
    for i in range(n-1, -1, -1):
      dp[i] = 1 # important because s[i..i] is a palindrome
      for j in range(i+1, n):
        if s[i] == s[j]:
          dp[j] = dp_prev[j-1] + 2
        else:
          dp[j] = max(dp[j-1], dp_prev[j])
      dp_prev = dp[:]
    return dp[-1]

  def lcs(s, t):
    # f(i,j) = length of lcs from s[0..i-1] and t[0...j-1]
    # need to compute f(i+1,j+1) after seeing s[i] and t[j]
    # transition rule:
    # f(i+1,j+1) = f(i,j) + 1 if s[i] = t[j]
    # f(i+1,j+1) = max(f(i+1,j), f(i,j+1))
    """ IMPORTANT THIS """
    # cannot be reduced to one dimension
    # f(j+1) = f(j) + 1 if s[i] == t[j] (need f(j) from previous iteration)
    # f(j+1) = f(j) (current iteration) + f(j+1) (previous iteration)
    # need to keep track of the previous row
    m, n = len(s), len(t)
    dp_prev, dp = [0] * (n + 1), [0] * (n + 1)
    for i in range(m):
      for j in range(n):
        if s[i] == t[j]:
          dp[j+1] = dp_prev[j] + 1
        else:
          dp[j+1] = max(dp[j], dp_prev[j+1])
      dp_prev = dp[:]
    return dp[-1]

def longestPalindromeSubstr(self, s: str) -> int:
  def lps(s):
    # f(i,j) = length of lps after seeing s[i+1...j-1]
    # need to compute f(i-1,j+1) after seeing s[i] and s[j]
    # transition rule:
    # f(i-1,j+1) = f(i,j) + 2 if s[i] == s[j] and f(i,j) = len(s[i+1...j-1])
    # f(i-1,j+1) = max(f(i-1,j), f(i,j+1)) otherwise
    # normalized equations
    # f(i,j) = f(i+1,j-1) + 2 if s[i] == s[j]
    # f(i,j) = max(f(i,j-1), f(i+1,j)) otherwise
    # need to fill rows from bottom to top
    # cannot remove dimension i
    # when state (i,j) is updated, we need to know
    #   j-1 from next row
    #   j-1 from current row and j from next row
    # so we need to keep track of the previous row
    n = len(s)
    dp_prev, dp = [0] * n, [0] * n
    start, size = 0, 1
    for i in range(n-1, -1, -1):
      dp[i] = 1
      for j in range(i+1, n):
        if s[i] == s[j] and dp_prev[j-1] == j-1-i:
          dp[j] = dp_prev[j-1] + 2
          if dp[j] > size:
            start = i
            size = dp[j]
        else:
          dp[j] = max(dp[j-1], dp_prev[j])
      dp_prev = dp[:]
    return s[start:start + size]
  return lps(s)

Knapsack

[leetcode.com] LC Discuss Post
[cp-algorithms.com] Knapsack Problem

[Similar to Bounded Knapsack] Count Ways to Target Sum

Expand Code

from functools import cache

def findTargetSumWays(self, nums: List[int], target: int) -> int:
  """
  IMPORTANT!! NEED TO KEEP IN MIND THAT RUNNING SUM HAS TO BE IN THE STATE.
  WE CANNOT MEMOIZE/USE DP IF WE KEEP THE RECURSIVE CALL STRUCTURE REDUCING
  TARGET. THAT METHOD IS NOT STATELESS AS COUNT CHANGES ACROSS CALLS.
  """
  def bounded_knapsack():
    # f(i, j) = number of ways to obtain target j after seeing i nums
    # f(0, 0) = 1
    # f(i+1, j) = f(i, j-nums[i]) + f(i, j+nums[i])
    # update rule: 
    # every f(i, j) would update f(i+1, j-nums[i]) and f(i+1, j+nums[i])
    """ 
    This is super important because if we loop the other way, we'd miss out on many updates.
    """
    # range for j: [-sum(abs(nums)), sum(abs(nums))]
    # range for i: 0...n-1
    # gotta be careful with offset
    n = len(nums)
    max_sum = sum(nums)
    if target > max_sum or target < -max_sum:
      return 0
    max_range = 2 * max_sum + 1
    dp = [[0] * max_range for _ in range(n + 1)]
    # dp[-][max_sum] actually represents curr sum = 0
    dp[0][max_sum] = 1 # important
    for i in range(n):
      """
      Incorrect way of doing it:
      for j in range(nums[i], max_range - nums[i]):
        dp[i+1][j] = dp[i][j-nums[i]] + dp[i][j+nums[i]]
      """
      # deciding on the range of j
      for j in range(nums[i], max_range - nums[i]):
        dp[i+1][j-nums[i]] += dp[i][j]
        dp[i+1][j+nums[i]] += dp[i][j]
    return dp[-1][max_sum + target]

  def memoized_with_annotation():
    @cache
    def dfs(index, curr_sum):
      if index == len(nums):
        return 1 if curr_sum == target else 0
      sub_curr = dfs(index + 1, curr_sum - nums[index])
      add_curr = dfs(index + 1, curr_sum + nums[index])
      return sub_curr + add_curr
    return dfs(0, 0)

  def memoized():
    # the idea is - every time we reach target 0 after seeing n numbers, we increase the count
    # memo dimension: index X max_range
    # note that the state here is current_sum as opposed to target
    # the reason is - to make the function calls stateless, we cannot use
    # reduced target as every time we call the same target the overall count
    # increases. on the other hand, current sum with the same index remains same
    # and hence can be memoized
    # range of curr_sum: 2*max_sum + 1
    # max_sum = 10, range: [-10,...-1, 0, 1,...10]
    #               index: [  0,    9,10,11,   21]
    max_sum = sum([abs(num) for num in nums])
    max_range = 2 * max_sum + 1
    memo = [[-1] * max_range for _ in range(len(nums))]

    def dfs(index, curr_sum):
      # not storing index=n entries because we only need 1
      if index == len(nums):
        return 1 if curr_sum == target else 0
      curr_sum_index = curr_sum + max_sum
      if memo[index][curr_sum_index] == -1:
        sub_curr = dfs(index + 1, curr_sum - nums[index])
        add_curr = dfs(index + 1, curr_sum + nums[index])
        memo[index][curr_sum_index] = sub_curr + add_curr
      return memo[index][curr_sum_index]

    return dfs(0, 0)

  def recursive_stateless():
    def dfs(index, curr_sum):
      if index == len(nums):
        return 1 if curr_sum == target else 0
      sub_curr = dfs(index + 1, curr_sum - nums[index])
      add_curr = dfs(index + 1, curr_sum + nums[index])
      return sub_curr + add_curr
    return dfs(0, 0)

  def recursive_with_external_variable():
    count = 0
    def dfs(index, curr_sum):
      nonlocal count
      if index == len(nums): # reached the end
        if curr_sum == target: # achieved the target
          count += 1
      else:
        dfs(index + 1, curr_sum - nums[index])
        dfs(index + 1, curr_sum + nums[index])
        # no need to do anything here as the state is updated on
        # reaching the target to the external variable
    dfs(0, 0)
    return count
  return bounded_knapsack()

Unbounded Fixed Target Sum [Backtracking]

Unbounded Knapsack: Coin Change

Expand Code

def coinChange(self, coins: List[int], amount: int) -> int:
  def unbounded_knapsack():
    # f(i, j) = min number of coins from the set coins[0...i] to make up for amount j
    # transition rule
    # f(i, j) = min(f(i-1, j), f(i, j-coins[i]) + 1)
    """ 
    if appears that we are only considering the case where we take coins[i] just once.
    but when we PROCESS THIS LEFT TO RIGHT, so, if f(i, j-k*coins[i]) really was
    the optimal ans for something we'd have considered it.
    
    !!!!!IMPORTANT!!!!!
    when the state (i,j) is updated, all (i,k<j) states should have been updated with
    the knowledge that coins[i] exists in this world!
    """
    # removing the first dimension
    # f(j) = min(f(j), f(j-coins[i]) + 1)
    n = len(coins)
    dp = [inf] * (amount + 1)
    dp[0] = 0
    for coin in coins:
      for j in range(coin, amount + 1):
        dp[j] = min(dp[j], dp[j-coin] + 1)
    return dp[-1] if dp[-1] < inf else -1

  def bfs_bottom_up():
    # the idea is to start traversing on the state transition
    # graph. start node is amount, and destination node is 0.
    # for each node in this graph, we have coins outgoing edges
    # O(V+E) = O(S+S*N)
    queue = deque([0])
    visited = set([])
    steps = 0
    while queue:
      size = len(queue)
      for _ in range(size):
        curr_amount = queue.popleft()
        if curr_amount == amount:
          return steps
        for coin in coins:
          new_amount = curr_amount + coin
          if new_amount <= amount and new_amount not in visited:
            queue.append(new_amount)
            visited.add(new_amount)
      steps += 1
    return -1
  def bfs_top_down():
    # the idea is to start traversing on the state transition
    # graph. start node is amount, and destination node is 0.
    # for each node in this graph, we have coins outgoing edges
    # O(V+E) = O(S+S*N)
    queue = deque([amount])
    visited = set([])
    steps = 0
    while queue:
      size = len(queue)
      for _ in range(size):
        curr_amount = queue.popleft()
        if curr_amount == 0:
          return steps
        for coin in coins:
          remaining_amount = curr_amount - coin
          if remaining_amount >= 0 and remaining_amount not in visited:
            queue.append(remaining_amount)
            visited.add(remaining_amount)
      steps += 1
    return -1

def coinChangeCountWays(self, amount: int, coins: List[int]) -> int:
  """ Note: f(i,j) = f(i-1,j) + f(i,j-coins[i]) """
  # f(i-1,j) := don't use j-th coin
  # f(i,j-coins[i]) := use j-th coin
  dp = [0] * (amount + 1)
  for coin in coins:
    dp[0] = 1
    for j in range(coin, amount + 1):
      dp[j] += dp[j-coin]
  return dp[-1]

Edit distance

Expand Code

def minEditDistance(self, word1: str, word2: str) -> int:
  # f(i,j) = edit distance after seeing s[0...i-1] and t[0...j-1]
  # f(i+1, j+1) = f(i, j) if s[i] == t[j]
  # else
  """ 
  Trick: 
    (1) Think of the next character we'd look after each operation.
    (2) Normalize the equations afterwards
  """
  # replace: f(i+1,j+1) = f(i,j) + 1
  # delete:  f(i+1,j) = f(i,j) + 1 => f(i+1,j+1) = f(i,j+1) + 1
  # insert:  f(i, j+1) = f(i,j) + 1 => f(i+1,j+1) = f(i+1,j) + 1
  """
  Final equations:
    f(i+1,j+1) = f(i,j) if s[i] == s[j] else (min(f(i,j),f(i,j+1),f(i+1,j))) + 1
  
  Cannot be reduced to lower dimensions - need both (i,j) and (i+1,j) at the same time
  """
  m, n = len(word1), len(word2)
  dp = [[0] * (n+1) for _ in range(m+1)]
  """ Key: IMPORTANT TO INITIALIZE PROPERLY """
  for i in range(m + 1):
    dp[i][0] = i # all delete
  for j in range(n + 1):
    dp[0][j] = j # all insert
  for i in range(m):
    for j in range(n):
      if word1[i] == word2[j]:
        dp[i+1][j+1] = dp[i][j]
      else:
        dp[i+1][j+1] = min(dp[i][j+1], dp[i+1][j], dp[i][j]) + 1
  return dp[-1][-1]

Expand Code

def maximalSquare(self, matrix: List[List[str]]) -> int:
  # if the current entry in the matrix is 1, then it can contribute
  # to 3 possible squares, one ending with top (i-1, j), one on the left
  # (i, j-1) and one ending on the corner (i-1, j-1)
  # case by case explanation:
  # if the square ending at (i-1, j) is the min, then we know for sure
  # that the one ending at (i, j-1) covers at least as many rows as (i-1, j). 
  # this is guaranteed since they are SQUARES not RECTANGLES.
  m, n = len(matrix), len(matrix[0]) if len(matrix) > 0 else 0
  prev_row = [1 if x == '1' else 0 for x in matrix[0]]
  curr_row = [0] * n
  result = max(prev_row)
  for i in range(1, m):
    curr_row[0] = 1 if matrix[i][0] == '1' else 0
    result = max(result, curr_row[0])
    for j in range(1, n):
      if matrix[i][j] == '1':
        curr_row[j] = min(curr_row[j-1], prev_row[j-1], prev_row[j]) + 1
        result = max(result, curr_row[j])
    for j in range(n):
      prev_row[j] = curr_row[j]
      curr_row[j] = 0
  return result * result
  
def maximalRectangle(self, matrix: List[List[str]]) -> int:
  # the approach for maximal square doesn't apply here
  # we solve it by folding it and forming histograms
  def max_consecutive_ones(arr):
    left = 0
    res = 0
    for right in range(len(arr)):
      if arr[right] == 0:
        left = right + 1
      else:
        res = max(right - left + 1, res)
    return res

  def largest_histogram(heights):
    # we scan from left to right and check the min of every interval
    # everything that gets popped is the min of some interval
    max_area = 0
    minstack = [-1]
    for i, height in enumerate(heights):
      while minstack[-1] != -1 and heights[minstack[-1]] >= height:
        prev_min_index = minstack.pop()
        # prev_min_index is the min of the range(stack[-1] + 1, i - 1)
        left, right = minstack[-1] + 1, i - 1 # IMPORTANT: THIS IS WHY WE NEED -1
        width = right - left + 1
        max_area = max(max_area, width * heights[prev_min_index])
      minstack.append(i)
    # everything that remains on stack is also min of some range
    while minstack[-1] != -1:
      prev_min_index = minstack.pop()
      # prev_min_index is the min of the range(stack[-1] + 1, n - 1)
      left, right = minstack[-1] + 1, len(heights) - 1
      width = right - left + 1
      max_area = max(max_area, width * heights[prev_min_index])
    return max_area

  m, n = len(matrix), len(matrix[0]) if len(matrix) > 0 else 0
  if not m or not n:
    return 0

  histogram = [1 if x == '1' else 0 for x in matrix[0]]
  max_area = max_consecutive_ones(histogram)
  for i in range(1, m):
    for j in range(n):
      histogram[j] = histogram[j] + 1 if matrix[i][j] == '1' else 0
    max_area = max(max_area, largest_histogram(histogram))
  return max_area

Word Break, Word Break 2

Expand Code

def wordBreak(self, s: str, wordDict: List[str]) -> bool:
  def good_approach():
    """ O(n*m*k) """
    # f(i) := s[0...i] can be segmented or not
    # f(i) = true of any f(j-1, j <= i) and s[j,i] in in dict
    words = set(wordDict)
    n = len(s)
    dp = [False] * n

    for i in range(n):
      for word in words:
        size = len(word)
        j = i-size+1
        if (j == 0 or (j > 0 and dp[j-1])) and (j >= 0 and s[j:i+1] == word):
          dp[i] = True
          break

    return dp[-1]

  def bad_approach():
    """ O(n^2) """
    # f(i) := s[0...i] can be segmented or not
    # f(i) = true of any f(j-1, j <= i) and s[j,i] in in dict
    words = set(wordDict)
    n = len(s)
    dp = [False] * n

    for i in range(n):
      for j in range(i+1):
        if (j == 0 or dp[j-1]) and s[j:i+1] in words:
          dp[i] = True
          break
    
    return dp[-1]
  
  return good_approach()

def wordBreakII(self, s: str, wordDict: List[str]) -> List[str]:
  def backtrack(curr, start_index):
    nonlocal result
    n = len(s)
    if start_index >= n:
      ans = ' '.join(curr)
      result.append(ans)
      return
    
    for j in range(start_index, n):
      if is_word(start_index, j):
        size = j - start_index + 1
        word = s[start_index: start_index + size]
        curr.append(word)
        backtrack(curr, start_index + size)
        curr.pop()
  
  def is_word(i, j):
    nonlocal words
    # curr = s[i:j+1]
    # return curr in words
  

  words = set(wordDict)
  n = len(s)
  # if dp[i][j] = True => s[i...j] is a valid word in the dict
  dp = [[False] * n for _ in range(n)]

  # TODO implement using trie
  print(dp)
  result = []
  backtrack([], 0)
  return result

Greedy¶

Single CPU Scheduling (Unordered With Delay Restrictions)

Expand Code

""" WHEN TASKS HAS TO BE EXECUTED IN ANY ORDER """
def taskScheduler(self, tasks: List[str], n: int) -> int:
  def heap_queue():
    # greedy:
    # since the order does not matter, pick the those teasks
    # in the decreasing order of counts.
    # 
    # IMPORTANT
    # process tasks with one tick at a time
    # to do that, we can maintain two data structures
    # (1) for the tasks which can be processed right away
    # (2) tasks which are in the queue to be available for processing later
    counts = Counter(tasks)
    # we don't need to reduce counts in the original dict
    # we can totally maintain the states using the two data structures we have
    # since we don't are about the type of the task, we don't need to keep
    # the task name as well
    # ready: priority queue -> counts
    # queued: counts, start_time
    ready = [-count for count in counts.values()]
    heapq.heapify(ready)
    queued = deque()
    curr_time = 0
    while ready or queued:
      if queued and queued[0][1] < curr_time:
        count, _ = queued.popleft()
        heapq.heappush(ready, count)
      if ready:
        count = 1 + heapq.heappop(ready)
        if count:
          queued.append((count, curr_time + n))
      curr_time += 1
    return curr_time

  def idle_counting():
    # visualisation:
    # 
  
  return heap_queue()

""" WHEN TASKS HAS TO BE EXECUTED IN GIVEN ORDER """
def taskSchedulerII(self, tasks: List[int], space: int) -> int:
  available_from = {}
  curr_day = 0
  for task in tasks:
    if task in available_from:
      """ IMPORTANT """
      # while doing timejump remember that we don't go back in past
      curr_day = max(curr_day, available_from[task]) # time jump
    curr_day += 1 # execute task
    available_from[task] = curr_day + space
  return curr_day

Resource Allocation

Expand Code

def canAttendAllMeetings(self, intervals: List[List[int]]) -> bool:
  def overlaps(first, second):
    return first[1] > second[0]

  n = len(intervals)
  # sort the intervals by start time
  # sorting helps because if any given interval (curr)
  # doesn't overlaps with the immediate next interval
  # then none of the next intervals would be overlapping with curr
  intervals.sort(key=lambda x:x[0])
  for i in range(1, n):
    if overlaps(intervals[i-1], intervals[i]):
      return False
  return True

def maxTimeMeetingRoomBooked(self, intervals: List[List[int]]) -> List[List[int]]:
  def overlaps(interval1, interval2):
    # since the calling ensures that interval1 has earlier start time
    # than interval2, we just need to check if interval1 ends after
    # interval2 begins.
    return interval1[1] >= interval2[0]
  
  def merge(interval1, interval2):
    # similar to above, the calling ensures that interval1 starts earlier
    # than interval2. therefore, for merged interval, we only need to check
    # the max of end times
    return [interval1[0], max(interval1[1], interval2[1])]

  intervals.sort()
  stack = [intervals[0]]

  for interval in intervals[1:]:
    if overlaps(stack[-1], interval):
      last = stack.pop()
      stack.append(merge(last, interval))
    else:
      stack.append(interval)

  return stack

def minMeetingsDropped(self, intervals: List[List[int]]) -> int:
  # removing overlapping intervals is a different prolem
  # than counting intervals.
  # why?
  # say, we have 3 intervals, i1, i2, i3 where i1 overlaps with i2
  # and i2 overlaps with i3. if we count overlaps, there are 2.
  # if we remove i1, overlap count reduces to 1
  # if we remove i3, overlap count reduces to 1
  # but if we remove i2, overlap count reduces to 0
  # so this requires a different strategy
  # greedy activity selection. basically the idea is to think of it
  # as meetings which are to be held in a single room. we are the doorman
  # and we want to maximize the room usage by assigning it to the most
  # number of meetings possible. this can be achieved by assigning it to
  # the meeting that ends first. since this choice doesn't hurt with the objective.
  intervals.sort(key=lambda x:x[1]) # sorted by end time
  n = len(intervals)
  meetings_count = 1
  last_meeting_finish_time = intervals[0][1]
  for start_time, finish_time in intervals[1:]:
    if last_meeting_finish_time <= start_time:
      meetings_count += 1
      last_meeting_finish_time = finish_time
  return n - meetings_count

def minMeetingRooms(self, intervals: List[List[int]]) -> int:
  # it asks for minimum number of resources that is required
  # to allocate all meetings. this means, every time there
  # are overlapping meetings, we need to find a new room to 
  # accomodate for it. if intervals are represented as nodes in
  # a graph, and we use edges to connect those nodes whenever they
  # are overlapping, then this problem can be thought of as a
  # graph colouring problem on that interval graph.
  # the algorithm works by simulation of the situation.
  # we need to maintain two lists - one for occupied rooms and one
  # for free rooms that we've already decided to pay for.
  # every time a new meeting comes, we first check if there are occupied
  # rooms which can be marked as free. we add them to the free rooms list.
  # we allocate room from this free list as we've already paid for them.
  # if there really are no free rooms, we increase max room count, and decide
  # to pay for one more extra room
  intervals.sort()
  occupied = [] # needs to store finish time
  # instead of free list, can we manage using just the count?
  free_rooms_count = 1
  max_rooms_used = 1

  for start_time, finish_time in intervals:
    while occupied and occupied[0] <= start_time:
      heapq.heappop(occupied)
      free_rooms_count += 1
    if free_rooms_count:
      heapq.heappush(occupied, finish_time)
      free_rooms_count -= 1
    else:
      max_rooms_used += 1
      heapq.heappush(occupied, finish_time)
  
  return max_rooms_used

def mostBooked(self, n: int, meetings: List[List[int]]) -> int:
  # here, the room id matters
  # need to maintain not just free rooms, but the room ids as well
  # lucky for us, our allocation rule indicates that we can pick
  # rooms from the free list in order of their ids.
  # so we maintain the same occupied and free lists. but we also
  # store the room ids.
  meetings.sort()
  occupied = [] # stores finish time and room id
  free = list(range(n)) # stores room id

  # we also need to do bookkeeping for meetings counts
  counts = defaultdict(int)

  for start_time, end_time in meetings:
    duration = end_time - start_time

    while occupied and occupied[0][0] <= start_time:
      _, room_id = heapq.heappop(occupied)
      heapq.heappush(free, room_id)
    
    if free:
      # can allocate a room right now
      room_id = heapq.heappop(free)
      heapq.heappush(occupied, (end_time, room_id))
      counts[room_id] += 1
    else:
      # need to wait until another room becomes free
      # need to adjust end time accordingly
      finish_time, room_id = heapq.heappop(occupied)
      heapq.heappush(occupied, (finish_time + duration, room_id))
      counts[room_id] += 1

  max_meetings = max(counts.values())
  # we return the room that held max meetings and has the lowest index
  # this can be achieved by traversing the key list in counts in sorted
  # order. lucky for us, dict already has keys in sorted order
  return [x for x in counts if counts[x] == max_meetings][0]

def busiestServers(self, k: int, arrival: List[int], load: List[int]) -> List[int]:
  # similar to meeting roms 3, here also we need to maintain
  # two lists for free resources and occupied resources
  # but unlike meeting rooms 3, where we were to wait until a room was free
  # and our preference was to allocate rooms to the lowest id possible,
  # here, we have a fixed allocation rule according to round robin.
  # if there are no free rooms at the time of arrival, request is dropped.
  # the round robin works on sorted room id sequences.
  # example:
  # at any given time, free rooms [0,1,5], and we have 8 resources [0-7]
  # request 12 comes. 12 % 8 = 4
  # if server 4 was available, we would have used it. but since it's not,
  # the next best we can do is 5. note that this is the insert position of 4
  # in the sorted free rooms list
  # does this hold for everything?
  # any incoming requests would be mapped to [0, 7] due to modulo division.
  # say, request 16 comes. server index = 16 % 8 = 0
  # since 0 is already there, we allocate it.

  # arrivals are already sorted
  occupied = [] # stores the finish time and room_id
  free = SortedList(list(range(k))) # stores room ids in sorted order
  # SortedList is a balanced BST
  # we could have used SortedSet since rooms are unique
  # but SortedList provides us with bisect_left which is what we need

  # bookkeeping for counts
  counts = defaultdict(int)

  for i, start_time in enumerate(arrival):
    end_time = start_time + load[i]

    while occupied and occupied[0][0] <= start_time:
      _, server_id = heapq.heappop(occupied)
      free.add(server_id)
    
    if free:
      # key point to observe here is that as long as we
      # have free servers, we can ALWAYS allocate resource
      # in a round robin fashion
      server_id = i % k
      index = free.bisect_left(server_id)
      # there is a server which can serve the request
      server_id = free[index] if index < len(free) else free[0]
      free.remove(server_id)
      heapq.heappush(occupied, (end_time, server_id))
      counts[server_id] += 1
  
  max_count = max(counts.values())
  # since keys in dict are in sorted order, this returns
  # the list of server ids in sorted order
  return [x for x in counts if counts[x] == max_count]