Greedy Algorithm - Example

A greedy algorithm is any algorithm that follows the problem solving heuristic of making the locally optimal choice at each stage with the hope of finding the global optimum.

Example: (Single Round Match 502 Round 1 - Division II, Level One)

為了 make the locally optimal choice at each stage, 我先把 requiredTime array 由小排到大，C# 的語法就是

Array.Sort(requiredTime);

PS. Array class 在 System namespace 底下，使用前記得 using System 或是直接呼叫 System.Array.Sort()。

---

整個程式碼如下:

public class TheProgrammingContestDivTwo {
  public int[] find(int T, int[] requiredTime) {
    Array.Sort(requiredTime);

    int elasped_time = 0;
    int solved = 0;
    int penalty = 0;
    for (int i = 0; i != requiredTime.Length; ++i) {
      if (elasped_time + requiredTime[i] <= T) {
        elasped_time += requiredTime[i];
        solved++;
        penalty += elasped_time;
      } else {
        break;
      }
    }

    return new int[] { solved, penalty };
  }
}