在 O(nlogn+mlogm) 中获得折扣的最大人数
maximum number of people that get a discount in O(nlogn+mlogm)
问题：
假设我们有 n 个人站在 x = 0 线上（none 站在同一个地方）并且我们在 x = 1 线上有 m 家商店。（none 位于同一地点）。每家商店都会给先到那家商店的人打折。例如，如果三个人同时先于其他人到达一家商店，那么他们三个都可以获得折扣。但是如果其中一个先到，另外两个后到，只有一个可以打折。
每个人选择最近的商店去，每个人的速度都一样。问题是找到一种贪心算法，即 returns 获得折扣的最大人数以及每个人必须去的商店，以获得 O(nlogn+mlogm).
中的结果
我的做法：
如果商店与人的距离相等并且此算法有效，事情就会变得复杂。唯一的问题是顺序是 O(nlogn+mlogm+nlogm)。我不知道如何改进它，或者是否有更好的算法可用于此问题，因此不胜感激。
在数学上，你可以很容易地证明：
O(n * log(n) + m * log(m)) = O(n * log(n) + m * log(m) + n * log(m))
因为对于任何 n ∈ N*，任何 m ∈ N* 下面的不等式成立：
n * log(n) + m * log(m) + n * log(m) < 2 *(n * log(n) + m * log(m))
这使您的解决方案符合预期的复杂性。
问题：
假设我们有 n 个人站在 x = 0 线上（none 站在同一个地方）并且我们在 x = 1 线上有 m 家商店。（none 位于同一地点）。每家商店都会给先到那家商店的人打折。例如，如果三个人同时先于其他人到达一家商店，那么他们三个都可以获得折扣。但是如果其中一个先到，另外两个后到，只有一个可以打折。
每个人选择最近的商店去，每个人的速度都一样。问题是找到一种贪心算法，即 returns 获得折扣的最大人数以及每个人必须去的商店，以获得 O(nlogn+mlogm).
我的做法：
如果商店与人的距离相等并且此算法有效，事情就会变得复杂。唯一的问题是顺序是 O(nlogn+mlogm+nlogm)。我不知道如何改进它，或者是否有更好的算法可用于此问题，因此不胜感激。
在数学上，你可以很容易地证明：
O(n * log(n) + m * log(m)) = O(n * log(n) + m * log(m) + n * log(m))
因为对于任何 n ∈ N*，任何 m ∈ N* 下面的不等式成立：
n * log(n) + m * log(m) + n * log(m) < 2 *(n * log(n) + m * log(m))
这使您的解决方案符合预期的复杂性。