CSC373 F24 作业1
截止日期：9月30日，午夜 指南：（请完整阅读！） 问题1.（11分） 在这个问题中，你将得到实线上的n个区间I1 = [a1, b1]，…，In = [an, bn]作为输入。每个区间$I_{j}$由两个数$a_{j}$和$b_{j}$指定。我们假设对于所有j，$a_{j} < b_{j}$。我们还假设没有两个区间共享它们的任何端点，即所有的数$a_{1}，…，a_{n}，b_{1}，…，b_{n}$都是不同的。这些区间在两个数组A[1…n]和B[1…n]中给出，其中$A[j] = a_{j}$，$B[j] = b_{j}$。 我们说区间$I_{j}$和$I_{k}$交叉，如果$I_{j} \cap I_{k} ≠ \emptyset$，但两个区间都不包含另一个。换句话说，如果$I_{k}$的恰好一个端点包含在$I_{j}$中，那么$I_{j}$和$I_{k}$交叉。 部分a.（3分）假设存在某个数x，使得对于所有j，$a_{j} < x$，并且对于所有j，$b_{j} > x$。给出一个在最坏情况下时间复杂度为$O(n log n)$的算法来计算满足$j < k$且$I_{j}$和$I_{k}$交叉的对数。证明你的答案。 提示：使用课堂上的一种分治算法。 部分b.（8分）给出一个分治算法来计算满足$j < k$且$I_{j}$和$I_{k}$交叉的对数，而不使用前一个子问题中的假设。你的算法应在最坏情况下的时间复杂度为$O(n log ^{2} n)$。证明你的答案。 部分c.（7分）（加分问题 – 可选）。修改你的算法，使其在最坏情况下的时间复杂度为$O(n log n)$。证明你的答案。 提示：尝试仅调用一次时间复杂度为$O(n log n)$的任何子例程，而不是递归调用。 问题2.（19分） 在这个问题中，你需要为k家杂货店确定位置，以服务于街道上的n所房屋。假设我们将街道建模为从0到1的区间，并且房屋的位置由实数$x_{1}，…，x_{n} \in [0,1]$给出。你可以假设$x_{1} < x_{2}… < x_{n}$，即位置是从左到右排序的，并且它们以数组$x[1…n]$的形式提供给你，其中$x[i] = x_{i}$。每周，每个房屋中的一个人会前往最近的杂货店购买食品杂货。你的目标是计算$y_{1}，…，y_{k} […]