Greedy Algorithm: Solving the Boats to Save People Problem

The Greedy Algorithm is a simple yet powerful technique used to solve optimization problems in computer science and programming, enabling computers to perform complex tasks efficiently. In this blog post, we will explain what a Greedy Algorithm is, how it works, and use it to solve the Boats to Save People problem, while also comparing its time complexity to a for loop approach.

What is a Greedy Algorithm?

For example, consider a scenario where you are trying to find the shortest path from one point to another. A Greedy Algorithm would choose the path that is closest to the destination at each step until it reaches the final destination. This may not always result in the absolute shortest path, but it is a quick and efficient way of finding a relatively short path.

Advantages of Greedy Algorithm

• Simplicity: The Greedy Algorithm is a simple algorithmic technique, making it easy to understand and implement.

• Efficiency: In many cases, the Greedy Algorithm is a very efficient way of solving optimization problems. It has a time complexity of O(n log n) in most cases, making it faster than brute force algorithms.

• Flexibility: The Greedy Algorithm can be used to solve a wide range of problems, including problems in computer science, operations research, and engineering.

Disadvantages of Greedy Algorithm

• Suboptimality: The Greedy Algorithm makes locally optimal choices at each step, without considering the future consequences. Therefore, it may not always lead to the globally optimal solution.

• Limited Applicability: The Greedy Algorithm is only suitable for solving problems that exhibit the greedy choice property, which means that making the locally optimal choice at each step will always lead to the globally optimal solution. Many problems do not exhibit this property.

• Difficulty of Proof: It can be challenging to prove that the Greedy Algorithm will always lead to the optimal solution. In some cases, it may require sophisticated mathematical proofs to show that the algorithm is correct.

When to use Greedy Algorithm

Greedy Algorithm should be used when the problem has the following properties:

1. The problem can be broken down into smaller subproblems that can be solved independently.

2. The optimal solution to the problem contains subproblems that also have optimal solutions.

3. The optimal solution to the problem can be obtained by making locally optimal (i.e., greedy) choices.

If the problem satisfies these properties, then a Greedy Algorithm can provide a fast and simple solution that finds a near-optimal solution. Generally, Greedy Algorithms are best used when the problem has a set of constraints that make locally optimal choices guarantee global optimality, and when a fast and simple solution is preferred over a more complex algorithm that may have better theoretical guarantees but is slower in practice.

The Boats to Save People Problem

Now, let's apply the Greedy Algorithm to solve a real-world problem called the Boats to Save People Problem.

The problem goes like this: You are given an array of people's weights and a boat that can carry a maximum weight of n pounds. You need to determine the minimum number of boats required to save all the people. Each boat can carry a maximum of two people at a time, provided the sum of their weights is at most n pounds.

To solve this problem using the Greedy Algorithm, we need to follow these steps:

1. Sort the array of people's weights in descending/ascend order.

2. Initialize two pointers, one at the beginning and one at the end of the array.

3. While the pointers do not cross each other: a. If the sum of the weights of the two people pointed by the pointers is less than or equal to n, increment the pointer at the beginning and decrement the pointer at the end. b. Otherwise, only decrement the pointer at the end.

4. Increment the boat count for each pair of people.

Let's look at an example to understand this better:

Suppose we have the following array of people's weights: [150, 80, 100, 110] and a weight limit of 300 lbs. We need to determine the minimum number of boats required to save all the people.

Using the Greedy Algorithm, we first sort the array in descending order: [150, 110, 100, 80].

Next, we initialize two pointers, one at the beginning and one at the end of the array:

1
[150, 110, 100, 80]
2
 ^              ^
3
beginning     ending

Since the sum of the weights of the two people pointed by the pointers is greater than 300, we decrement the pointer at the end:

1
[150, 110, 100, 80]
2
 ^         ^
3
beginning  ending

The sum of the weights of the two people pointed by the pointers is less than or equal to 300, so we increment the pointer at the beginning and decrement the pointer at the end:

1
[150, 110, 100, 80]
2
       ^    ^
3
 beginning ending

Since the sum of the weights of the two people pointed by the pointers is less than or equal to 300, we increment the pointer at the beginning and decrement the pointer at the end:

1
[150, 110, 100, 80]
2
       ^    ^
3
   ending  beginning

Now, the pointers have crossed each other, and we have saved all the people using two boats.

Time Complexity Comparison

Now, let's compare the time complexity of using a for loop versus using the Greedy Algorithm to solve the Boats to Save People Problem.

If we were to solve this problem using a for loop, we would iterate through the array of people's weights, selecting pairs of people whose sum is less than or equal to 300. This approach has a time complexity of O(n^2), where n is the number of people. Below is a code example using a for loop:

1
function numBoatsForLoop(people) {
2
  people.sort((a, b) => b - a);
3
  let numBoats = 0;
4
  let used = new Array(people.length).fill(false);
5
  for (let i = 0; i < people.length; i++) {
6
    if (!used[i]) {
7
      used[i] = true;
8
      let weightLeft = 300 - people[i];
9
      for (let j = i + 1; j < people.length; j++) {
10
        if (!used[j] && people[j] <= weightLeft) {
11
          used[j] = true;
12
          weightLeft -= people[j];
13
          break;
14
        }
15
      }
16
      numBoats++;
17
    }
18
  }
19
  return numBoats;
20
}

On the other hand, the Greedy Algorithm has a time complexity of O(n log n), where n is the number of people. The time complexity is dominated by the sorting step, which takes O(n log n) time. Once the array is sorted, we only need to iterate through it once, making the algorithm much faster than using a for loop. Below is a code example using the Greedy algorithm:

1
function numBoatsGreedy(people) {
2
  // sort the array of weights from lightest to heaviest
3
  people.sort((a, b) => b - a);
4
  let numBoats = 0;
5
  let minPointer = 0, maxPointer = people.length - 1;
6
  while (minPointer <= maxPointer) {
7
    if (people[minPointer] + people[maxPointer] <= 300) {
8
      i++;
9
    }
10
    j--;
11
    numBoats++;
12
  }
13
  return numBoats;

Related Problems with Greedy Algorithm

1. Activity Selection Problem

2. Fractional Knapsack Problem

3. Huffman Coding Problem

4. Coin Change Problem

5. Interval Scheduling Problem

Conclusion

The Greedy Algorithm is a simple yet powerful algorithmic technique used to solve optimization problems. It works by making the locally optimal choice at each step, without worrying about the future consequences. We applied this algorithm to solve the Boats to Save People Problem and compared its time complexity to using a for loop. The Greedy Algorithm was much faster, making it a more efficient way of solving this problem.