chapterGreedy.tex

% !TEX root = algo-quicksheet.tex
\chapter{Greedy}

\section{Introduction}
Philosophy: choose the best options at the current state without backtracking/reverting the choice in the future. 

A greedy algorithm is an algorithm that follows the problem solving heuristic of making the \textbf{local optimal} choice at each stage with the hope of finding a global optimum.

Greedy algorithm is a degraded DP since the the past substructure is not remembered.

\subsection{Proof}
The proof technique for the correctness of the greedy method. 

Proof by contradiction, the solution of greedy algorithm is $\mat{G}$ and the optimal solution is $\mat{O}$, $\mat{O}\neq \mat{G}$ (or relaxed to $|\mat{O}|\neq |\mat{G}|$). 

Two general technique it is impossible to have $\mat{O}\neq \mat{G}$:
\begin{enumerate}
\item \rih{Exchange method}: Greedy-Choice Property. Any optimal solution can be transformed into the solution produced by the greedy algorithm without worsening its quality.  
\item \rih{Stays-ahead method}: Optimal Substructure. the solution constructed by the greedy algorithm is consistently as good as or better than any other solution at every step or position
\end{enumerate}

\section{Extreme First}
\runinhead{Schedule jobs with duration and deadlines.} Given a list of jobs $A$ and each $A_i$ has a (duration, deadline). Determine whether we can finish all the jobs. 

Greedily choose the earliest deadline. Why earliest-deadline-first is the only schedule we need to test? 
\begin{enumerate}
\item Deadline inversions are harmless to fix. Call an \textbf{inversion} two consecutive jobs $A_i, A_j$ where the first one’s $A_i$ deadline is later than the second one’s $A_j$ . \textbf{Swap} such a pair.
\item $A_j$ with the earlier deadline now finishes \textbf{sooner}, so it meets its deadline. 
\item $A_i$ \textbf{inherits} $A_j$'s old completion time ($A_i.t + A_j.t = A_j.t + A_i.t$) and $A_i$ has a later deadline; thus $A_i$ can finish. 
\item $\Ra$ Result: a swap never turns a feasible schedule into an infeasible one.
\end{enumerate}


\runinhead{Rearranging String $k$ distance apart.} Given a non-empty string $s$ and an integer $k$, rearrange the string such that the same characters are at least distance
$k$ from each other.

\textbf{Core clues.} 
\begin{enumerate}
\item The char with the most count put to the result first - greedy.
\item Fill every $k$ slots as cycle - greedily fill high-count char as many as possible.
\end{enumerate}

\textbf{Implementations.}
\begin{enumerate}
\item Use a heap as a way to get the char of the most count. 
\item \pyinline{while} loop till exhaust the heap
\end{enumerate}

\begin{python}
def rearrangeString(self, s, k):
  if not s or k == 0: return s

  d = defaultdict(int)
  for c in s:
    d[c] += 1

  h = []
  for char, cnt in d.items():
    heapq.heappush(h, Val(cnt, char))

  ret = []
  while h:
    cur = []
    for _ in range(k):
      if not h: 
        return "".join(ret) if len(ret) == len(s) else ""

      e = heapq.heappop(h)
      ret.append(e.val)
      e.cnt -= 1
      if e.cnt > 0:
        cur.append(e)

    for e in cur:
      heapq.heappush(h, e)

  return "".join(ret)

\end{python}
\subsection{Coverage}
\runinhead{Minimum to cover.} Given $n$ representing the garden starts at the point 0 and ends at the point $n$. An array $ranges$ of length $n + 1$ where $ranges_i$  means the i-th tap can water the area $[i - ranges_i, i + ranges_i]$

Find the minimum number of taps that should be open to water the whole garden. 

\rih{Core clues:}
\begin{enumerate}
\item Each ranges cover $[start, end]$ $\Ra$ need a map either by start or end. 
\item Minimum taps to cover is maximum covering range $\Ra$ greedy 
\end{enumerate}
\begin{python}
def minTaps(self, n, ranges):
  # reaches: max end by start
  reaches = [0 for _ in range(n + 1)]
  for i, r in enumerate(ranges):
    s = max(0, i - r)
    e = min(n+1, i + r + 1)  # [i-r, i+r+1)
    reaches[s] = max(reaches[s], e)

  ret = 0
  lo, hi = 0, 1 # [lo, hi)
  maxa = hi
  # Greedily extend coverage until we reach n
  while maxa <= n:
    # search for one tap that reaches farthest
    for i in range(lo, hi):
      maxa = max(maxa, reaches[i])

    # cannot extend coverage
    if maxa <= hi:
      return -1
    ret += 1

    lo = hi
    hi = maxa

  return ret
\end{python}

Note that the dictionary name can be short form by keys as \pyinline{starts} or values as \pyinline{reaches} and the latter is preferred.