分治算法代写 | Divide And Conquer Algorithm

本次加拿大代写是分治算法的一个练习题

A more general problem is to find non-dominated boxes. The input is a set of boxes B1, . . . ,Bn,
where each box Bi is given as a triple (li, ri, yi) and consists of all the points (x, y) with
ℓi ≤ x ≤ ri and y ≤ yi. Note that these boxes extend downwards forever. A box Bi is
non-dominated if there is some point in Bi that is not in any Bj , j = i, or equivalently, if
there is some exposed point on the top boundary of Bi that is not in any Bj , j = i. The
output should be the list of the corner points along the exposed top boundary. See Figure
1b.

Figure 1: (a) non-dominated points. (b) input boxes B1, . . . ,B4. (c) the exposed top boundary
q1, . . . , q8. The non-dominated boxes are B2, B3, B1.

(c) [10 marks] Give an O(n log n) time divide and conquer algorithm for the non-dominated
boxes problem.


程序代写代做C/C++/JAVA/安卓/PYTHON/留学生/PHP/APP开发/MATLAB


blank

本网站支持淘宝 支付宝 微信支付  paypal等等交易。如果不放心可以用淘宝交易!

E-mail: itcsdx@outlook.com  微信:itcsdx


如果您使用手机请先保存二维码,微信识别。如果用电脑,直接掏出手机果断扫描。

blank

发表评论