java - 合并 n 个列表并对数据进行排序，保持原始顺序/约束

Question

我在编码竞赛中遇到了以下问题。我尝试了很多，但一个私有(private)测试用例总是因错误的答案而失败，我无法弄清楚为什么我的以下方法会失败。我没有天真的解决方案来生成压力测试用例并进行比较。此外，不会发表任何社论。因此，如果可能的话，我正在找人指出我方法中的缺陷。

以下是对问题的详细描述以及我到目前为止所做的尝试。

问题:有多个地区，您会根据学生在各自地区的排名为每个地区的学生打分。例如:

Region1:
StudentName, Score
A,           50.0
B,           60.0  
C,           40.0 

Region2:
StudentName, Score
D,           30.0
E,           10.0
F,           20.0 

在上面的数据中，学生A在Region1中排名为1，B在Region1中排名为2，C在Region1中排名为3。同理，D在Region2有Rank1，E有Rank2，F有Rank3。

• 学生可能得分较低，但在同一地区的排名仍然较高。例如，A 在 Region1 中的排名比 B 高，即我们应该假设每个区域的数据已经根据排名排序。

我们的任务是合并所有地区的数据并创建一个根据分数排名的全局数据。约束是任何在该地区排名较低的学生的排名仍然不能高于其所在地区在原始地区数据中排名比它更好的其他学生。

例如:

Region1:
A, 50.0
B, 60.0
C, 40.0 

Region2:
D, 30.0
E, 10.0
F, 20.0

将合并到:

A, 50.0
B, 60.0
C, 40.0 
D, 30.0
E, 10.0
F, 20.0

顺序不会根据分数而改变，因为根据区域限制，B 始终低于 A，F 始终低于 E。

其他测试用例:

Region1:
A, 50.0
B, 60.0
C, 70.0 

Region2:
D, 30.0
E, 20.0
F, 10.0

结果还是按照A,B,C,D,E,F的顺序

Region1:
A, 60.0
B, 80.0
C, 100.0 

Region2:
D, 70.0
E, 90.0
F, 110.0

将导致:D、E、F、A、B、C

但是，

Region1:
A, 11.5
B, 8.5
C, 10.0 

Region2:
D, 12.0
E, 9.0
F, 9.5

将导致:

D, 12.0
A, 11.5
E, 9.0 
B, 8.5
C, 10.0
F, 9.5

Constraints:
1<=number of regions<=6
score can be upto 7 decimal places

我的方法是将所有输入数据添加到一个列表并保持稳定排序，即如果两个学生的区域相同，则比较他们在区域中的排名，否则比较分数。

static class Student implements Comparable<Student>
{
String name;
double score;
int zone;
int rank;

//constructor

public int compareTo(Student o)
{
if(this.zone == o.zone)
{
//lower i.e. better rank
return Integer.compare(this.rank, o.rank);
}
//higher i.e. better score
return Double.compare(o.score, this.score);
}

}

main()
{
//read data from console input into an ArrayList<Student> students
Collections.sort(students);
//print each student from students

}

这个问题没有提到两个学生在不同区域的分数是否相等。在那种情况下，我尝试使用他们在该区域中的各自等级来打破平局，但私有(private)测试用例一直失败。我最初认为这个问题可能缺少一些信息，但我在竞赛仪表板中看到许多关于这个问题的成功提交。这就是我认为我遗漏了一些东西并且问题并不像我想的那么简单的原因。但是，我无法想出一个测试用例来验证这个假设。

谢谢!

Answer 1

据我了解这个问题，要求是根据分数对学生进行排序，但有一个额外的限制，即保留区域内学生的相对顺序。

给定问题中所列示例之一的输入数据，

Region1:
A, 11.5
B, 8.5
C, 10.0 

Region2:
D, 12.0
E, 9.0
F, 9.5

仅按分数排序会得到以下结果:DACFEB。

但是，关于在区域内保持相对顺序的约束需要以下部分顺序 A < B < C 和 D < E < F。

OP 将此特定示例的解决方案作为 DAEBCF 提供。在对这个问题的评论中，我为这个例子提出了另外两种可能的解决方案:DABCEF 和 DAEFBC。我看不到任何标准可以让我们决定这些可能的解决方案中哪一个是正确的。因此，问题是欠约束的。人们可以争论这些解决方案中哪一个比其他解决方案更可取，但这样做会引入新的限制，而这些限制在原始问题中并不明显。

鉴于有多个解决方案满足问题中的所有条件，这意味着该域中的值没有总排序。此外，鉴于正确的比较器必须对其域的值进行总排序，因此不可能为该域编写适当的比较器。

当然，可以编写一个具有某些行为的正确比较器，并且它会优先于这些可能的解决方案中的一个而不是其他解决方案。这样做将隐含地实现不属于问题陈述一部分的额外约束。事实上，看起来 Vincent van der Weele已经这样做了。声明“下一个空位必须由其中一个区域中排名最高的剩余元素填充。哪个？得分最高的”引入了附加约束。它导致订购 DAEBCF，这是 OP 建议的。虽然这是明智的，但它必然是“正确”的顺序。

替代算法可能如下所示。 1) 从一个空的结果列表开始，并按排名顺序维护来自每个地区的学生列表。 2) 找到剩下的得分最高的学生。 3) 将该学生和同一地区内排名较高的学生附加到结果中，保持相对顺序。 4) 重复直到没有学生留下。

将此算法应用于 DABCEF 中的示例输入结果。这是明智的，但以不同的方式。同样，我们不知道这是否是“正确”答案。

要么是编程竞赛中的问题一开始就没有明确说明，要么是竞赛的问题陈述与 OP 在 Stack Overflow 上的问题之间丢失了一些信息。