Greedy Algorithms and Invariants

Prev: Dynamic Programming Next: Graphs

Problems

18.1

We consider the problem of assigning tasks to workers. Each worker must be assigned exactly two tasks. Each task takes a fixed amount of time, and the tasks are independent. Any task can be assigned to any worker.

We want to assign tasks to workers so as to minimize how long it takes before all tasks are completed. For example, if there are 6 tasks whose durations are 5, 2, 1, 6, 4, and 4 hours, an optimum assignment is to pair $(5,2)$, $(1,6)$, and $(4,4)$, for a completion time of $\max (5+2,1+6,4+4)=8$ hours.

Design an algorithm that takes as input a set of tasks and returns an optimum assignment.

Hint: What additional task should be assigned to the worker who is assigned the longest task?

---

18.2

A database has to respond to a set of client SQL queries. The service time required for each query is known in advance. The queries must be processed one at a time, but may be processed in any order. The waiting time of a query is the time it spends waiting before its turn comes.

Given service times for a set of queries, compute a schedule that minimizes the total waiting time. Return the minimum total waiting time. For example, if the service times are $⟨2,5,1,3⟩$, then in the given order the total waiting time is $0+2+(2+5)+(2+5+1)=17$, whereas the minimum possible total waiting time is 10.

Hint: Focus on extreme values.

---

18.3

Consider a foreman responsible for a number of tasks on the factory floor. Each task starts at a fixed time and ends at a fixed time. The foreman wants to visit the floor to check on the tasks, and in each visit he can check on all tasks taking place at that exact time. A visit takes place at a fixed time.

You are given a set of closed intervals. Design an efficient algorithm for finding a minimum-sized set of numbers that covers all the intervals. For example, if the intervals are $[0,3],[2,6],[3,4],[6,9]$, then $\{3,6\}$ is a minimum set of visit times covering them all.

Hint: Think about extremal points.

Variant: You are responsible for the security of a castle with a circular perimeter. A total of $n$ robots patrol the perimeter, each along a closed arc, and you want to monitor them by installing cameras at the center that look out along rays. Minimize the number of cameras.

Variant: There are a number of points in the plane that you want to observe. You are located at the point $(0,0)$, may rotate about this point, and your field-of-view is a fixed angle. Which direction should you face to maximize the number of visible points?

---

18.4

Design an algorithm that takes as input an array and a number, and determines if there are three entries in the array, not necessarily distinct, which add up to the specified number. For example, if the array is $⟨11,2,5,7,3⟩$, then there are three entries summing to 21, but no three entries sum to 22.

Hint: How would you check if a given array entry can be added to two more entries to get the specified number?

Variant: Solve the same problem when the three elements must be distinct.

Variant: Solve the same problem when $k$, the number of elements to sum, is an additional input.

Variant: Write a program that takes as input an array of integers $A$ and an integer $T$, and returns a 3-tuple $(A[p],A[q],A[r])$, where $p,q,r$ are all distinct, minimizing $|T-(A[p]+A[q]+A[r])|$.

Variant: Write a program that takes as input an array of integers $A$ and an integer $T$, and returns the number of 3-tuples $(p,q,r)$ such that $A[p]+A[q]+A[r]\le T$ and $A[p]\le A[q]\le A[r]$.

---

18.5

Several applications require identifying elements in a sequence which occur more than a specified fraction of the total number of elements. Here we consider the special case where more than half the strings in the input are repetitions of a single string, called the majority element.

You are reading a sequence of strings. You know a priori that more than half the strings are repetitions of a single string, but the positions where it occurs are unknown. Write a program that makes a single pass over the sequence and identifies the majority element. For example, if the input is $⟨b,a,c,a,a,b,a,a,c,a⟩$, then $a$ is the majority element.

Hint: Take advantage of the existence of a majority element to perform elimination.

---

18.6

In the gasup problem, a number of cities are arranged on a circular road. You need to visit all the cities and come back to the starting city. A certain amount of gas is available at each city. The total amount of gas summed over all cities is equal to the amount of gas required to go around the road. Your gas tank has unlimited capacity. Call a city ample if you can begin at that city with an empty tank, refill at it, then travel through all remaining cities, refilling at each, and return to the ample city without running out of gas.

Given an instance of the gasup problem, compute an ample city efficiently. You may assume that there exists an ample city.

Hint: Think about starting with more than enough gas to complete the circuit without gassing up. Track the amount of gas as you perform the circuit, gassing up at each city.

Variant: Solve the same problem when you cannot assume that there exists an ample city.

---

18.7

An array of integers naturally defines a set of vertical lines parallel to the $Y$-axis, starting from $x=0$. The goal is to find the pair of lines that together with the $X$-axis trap the most water.

Write a program that takes as input an integer array and returns the pair of entries that trap the maximum amount of water.

Hint: Start with 0 and $n-1$ and work your way in.

---

18.8

You are given a sequence of adjacent buildings. Each has unit width and an integer height. These buildings form the skyline of a city.

Let $A$ be an array representing the heights of adjacent buildings of unit width. Design an algorithm to compute the area of the largest rectangle contained in this skyline.

Hint: How would you efficiently find the largest rectangle which includes the $i$th building and has height $A[i]$?

Variant: Find the largest square under the skyline.

Answers

18.1

Sort the task durations, then pair the shortest remaining task with the longest remaining task, the second shortest with the second longest, and so on. This balances the worker loads as tightly as possible and yields an optimum assignment in $O(n\log n)$ time.

---

18.2

Serve the shortest queries first. Each query’s service time contributes to the waiting time of every query after it, so moving a shorter job earlier can only help. Sorting by nondecreasing service time and summing prefix contributions gives the minimum total waiting time in $O(n\log n)$ time.

---

18.3

Sort the intervals by right endpoint. Repeatedly pick the smallest right endpoint of any uncovered interval, add it to the answer, and discard all intervals it covers. This greedy rule is optimal because any cover must include a point in the earliest-finishing interval, and choosing its right endpoint covers as many future intervals as possible. The running time is $O(n\log n)$.

---

18.4

Sort the array and, for each entry $A[i]$, solve a 2-sum problem on the remaining search range for target $t-A[i]$ using the standard two-pointer invariant. This gives $O(n^2)$ time after sorting and $O(1)$ extra space. Hashing also works, but the sorted two-pointer version is cleaner here.

---

18.5

Use Boyer-Moore majority vote. Keep a candidate and a counter. When the counter is zero, adopt the current string as candidate. When the next string matches the candidate, increment the counter; otherwise decrement it. Since majority and non-majority strings can be paired off and discarded, the surviving candidate is the majority element. This is $O(n)$ time and $O(1)$ space.

---

18.6

Track the running gas surplus as you traverse the circle. The key observation is that an ample city is one where the running surplus is minimized just before refueling there; starting there shifts the entire surplus graph upward so it never goes negative. One pass suffices, so the algorithm is $O(n)$ time and $O(1)$ space.

---

18.7

Start with the widest possible pair, the first and last lines. The trapped water is width times the smaller of the two heights. If the left line is shorter, no better answer can use it with any inward partner, so move the left pointer right; symmetrically move the right pointer left when the right line is shorter. This two-pointer invariant gives an $O(n)$ algorithm.

---

18.8

Maintain a stack of indices with increasing building heights. When a new building is lower than the stack top, repeatedly pop blocked heights and compute the maximal rectangle each popped height can support, using the new index as the right boundary and the next stack element as the left boundary. Push each index once and pop it once, so the total time is $O(n)$ and the space is $O(n)$.