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

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

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

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

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