合并 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 在 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

}

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

Answer 1

据我了解这个问题，要求是根据分数对学生进行排序，但还有一个额外的限制是要保留一个区域内学生的相对顺序。鉴于问题中列出的示例之一的输入数据，Region1:A, 11.5B, 8.5C, 10.0&nbsp;Region2:D, 12.0E, 9.0F, 9.5仅按分数排序会得出以下结果：DACFEB。然而，关于在一个区域内保持相对排序的约束需要以下部分排序A < B < C 和 D < E < F。OP 将此特定示例的解决方案称为 DAEBCF。在对该问题的评论中，我为此示例提出了另外两种可能的解决方案：DABCEF 和 DAEFBC。我没有看到任何标准可以让我们决定哪些可能的解决方案是正确的。因此，该问题受到了不足的约束。人们可以争论这些解决方案中的哪一个比其他解决方案更可取，但这样做会引入新的约束，而这些约束在原始问题中并不明显。鉴于有多个解决方案满足问题中的所有标准，这意味着该域中的值没有完全排序。此外，鉴于正确的比较器必须对其域的值进行总排序，因此不可能为该域编写适当的比较器。当然，可以编写一个正确的比较器，它有一些行为，并且会更喜欢这些可能的解决方案之一而不是其他解决方案。这样做将隐含地实施不属于问题陈述的附加约束。事实上，Vincent van der Weele似乎已经这样做了。语句“下一个空白点必须由其中一个区域的排名最高的剩余元素填充。哪个？得分最高的那个”引入了附加约束。它导致了 OP 建议的排序 DAEBCF。虽然这是明智的，但它必然是“正确”的排序。另一种算法可能如下。1）从一个空的结果列表开始，并按排名顺序维护来自每个地区的学生列表。2) 找出剩下的得分最高的学生。3) 取该学生和同一区域内排名较高的学生，并将它们附加到结果中，保持相对顺序。4) 重复直到没有学生留下。将此算法应用于示例输入会产生 DABCEF。这是明智的，但方式不同。同样，我们不知道这是否是“正确”的答案。要么是编程竞赛中的问题一开始就没有明确说明，要么是竞赛的问题陈述与 Stack Overflow 上 OP 的问题之间丢失了一些信息。

Answer 2

您的比较器不正确。您基本上说，如果学生来自同一地区，则按排名排序，否则按分数排序。但事实并非如此，如本例所示：Region1:A, 11.5B, 8.5C, 10.0&nbsp;Region2:D, 12.0E, 9.0F, 9.5结果是D, 12.0A, 11.5E, 9.0&nbsp;B, 8.5C, 10.0F, 9.5即，得分为 9.0 的 E 排在得分为 10.0 的 C 之前，即使他们来自不同的地区。一个更简单的算法，它确实有效：逐个元素填充结果。下一个空位必须由其中一个区域中排名最高的剩余元素填充。哪一个？得分最高的那个。因此，从其区域中删除该元素，将其添加到结果中，然后重复直到完成。