假定您正在用各种轨道导弹将任何东西摧毁的防御力，来保护各种长度的战舰的海滩。战列舰位于x，y网格上，并具有2个面的参数（x1，x2，y）和y坐标。您只有有限的资源，并且需要尝试使用最少数量的将被放置在x坐标上的轨道炮消灭所有战列舰。
如果x1
当前我要解决的方法是在下沉大多数船只的位置添加轨道炮，然后从列表中删除这些船只，然后在更新的列表中寻找下沉最多船只的下一个位置，依此类推，直到没有船只剩下。但是我发现了一个反例。
我对其他最佳解决方案不知所措。
lijunlove 回答：如何为该冲突问题创建最佳解决方案？
您的标签包括greedy。贪婪的方法可能看起来像这样：
对x坐标的开始和结束以及相应的船只索引进行排序。
遍历完成列表。如果标记了当前项目索引-忽略它，否则标记所有起始项目的索引直到当前坐标，然后在当前坐标处触发。
对于给定的示例，您将在3、6和8点开火
三个列表/数组。一个包含对(start[i]; i)，另一个包含对(end[i]; i)，第三个包含boolean[N]标记。
对于船（0,3,1），结束列表中的第一项是3。因此，我们发射并杀死（mark）船只（0,1），（1,4,0）和（1,4），因为它们的起始距离小于3。