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

Question

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

下面是对问题的详细描述，以及我迄今为止所做的尝试。

问题:有多个区域，您将根据每个区域的学生在各自区域中的排名获得分数。例如:

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在区域1中排名1，B在区域1排名2，C在区域1排3。同样，D在区域2排名1，E排名2，F排名3。

• 学生在同一地区的分数可能较低，但排名仍然较高。例如，A在区域1中的排名比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

}

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

谢谢！

Answer 1

你的比较器不正确。你基本上说学生如果来自同一个地区就按排名排序，否则就按分数排序。但这不是真的，正如这个例子所示:

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

即得分为9.0的E在得分为10.0的C之前，即使它们来自不同的地区。

一个更简单的算法：

逐元素填充结果。下一个空位必须由其中一个区域中排名最高的剩余元素来填充。哪一个？得分最高的那个。因此，将该元素从它所在的区域中移除，将其添加到结果中，并重复直到完成。

Answer 2

按照我对这个问题的理解，要求是根据分数对学生进行排序，但附加的约束条件是保持学生在一个区域内的相对排序。

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

Region1:
A, 11.5
B, 8.5
C, 10.0 

Region2:
D, 12.0
E, 9.0
F, 9.5

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

但是，关于在区域内保留相对顺序的约束需要以下部分排序 A

OP给出了作为DAEBCF的这个特殊例子的解决方案。在对这个问题的评论中，我为这个例子提出了另外两个可能的解决方案:DABCEF和DAEFBC。我看不出有什么标准可以让我们决定这些可能的解决方案中哪一个是正确的。因此，这个问题是欠约束的。人们可以争论这些解决方案中哪一个更好，但是这样做会引入新的约束，而这些约束在最初的问题中并不明显。

假设有多个解决方案满足问题中的所有标准，这意味着该域中没有值的总排序。此外，鉴于正确的比较器必须对其域的值施加总排序，因此不可能为该域编写正确的比比器。

当然，可以编写一个具有某些行为的正确比较器，并且该比较器更喜欢这些可能的解决方案之一而不是其他解决方案。这样做将隐式实现不属于问题陈述的其他约束。事实上，文森特·范德韦勒似乎已经这样做了。声明“下一个空白点必须由其中一个区域中排名最高的剩余元素填补。哪一个？得分最高的那个“引入了额外的约束。它导致排序DAEBCF，这是OP建议的。虽然这是明智的，但它必然是“正确”的排序。

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

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

要么是编程竞赛中的问题一开始就没有明确说明，要么是在竞赛的问题陈述和OP关于堆栈溢出的问题之间丢失了一些信息。