座位分配贪心策略正确性咨询：求失败测试用例及优化建议

问题背景 #

我正在解决Kattis平台上的「distributingseats」问题，该问题被Steven & Felix所著《竞赛编程手册》列为经典贪心问题。题目给出的提示包括：

• 排序
• 贪心二分匹配
• 优先将乘客分配到最早可用的行

当前核心难点是确定正确的排序依据。

实现情况与问题 #

我的实现仅通过了19个测试用例中的3个，具体思路如下：
每位乘客有可接受的行区间，我尝试按区间右端点排序，右端点相同时按左端点排序。该策略能通过题目样例及我自行构造的测试用例（见测试用例截图），但我需要一个能触发失败的测试用例来排查问题。

Java实现代码 #

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt();
    int r = scanner.nextInt();
    int c = scanner.nextInt();

    int a, b, s;
    List < int[] > L = new ArrayList < > ();

    for (int i = 0; i < n; ++i) {
      a = scanner.nextInt() - 1;
      b = scanner.nextInt() - 1;
      s = scanner.nextInt();
      L.add(new int[] {
        Math.max(0, a - s), Math.min(r - 1, a + s)
      });
    }

    L.sort((x, y) -> {
      if (x[1] == y[1]) {
        return Integer.compare(x[0], y[0]);
      }
      return Integer.compare(x[1], y[1]);
    });

    int ans = 0;
    int idx = 0;

    for (int i = 0; i < r; ++i) {
      for (int j = 0; j < c; ++j) {
        while (idx < L.size() && L.get(idx)[1] < i) {
          ++idx;
        }
        if (idx == L.size()) {
          break;
        }
        if (L.get(idx)[0] <= i && i <= L.get(idx)[1]) {
          ++ans;
          ++idx;
        }
      }
    }

    System.out.println(ans);
  }

}

内容的提问来源于stack exchange，提问作者musashi