You are designing background art for a video game in the form of a cityscape. Yo

Question

You are designing background art for a video game in the form of a cityscape. You are given a list of n buildings. Building B_i is represented as a triplet (L_i, H_i, R_i) where L_i and R_i denote the left and right x coordinates of the building, and H_i denotes the height of the building. The cityscape for this problem is an outline of all the buildings put together when seen against a backdrop. It is represented as a list of x coordinates along with the height from that coordinate to the next, arranged in order from left to right. (Note that the list is of length at most 4n.) Example: (See picture below.) The cityscape for the buildings in the list {(3, 13, 9), (24, 4, 28), (19, 18, 22), (1, 11, 5), (12, 7, 16), (14, 3, 25), (2, 6, 7), (23, 13, 29)} is given by {(1, 11), (3, 13), (9, 0), (12, 7), (16, 3), (19, 18), (22, 3), (23, 13), (29, 0)}. Let the size of a cityscape be the number of elements (tuples) in its list. Describe an algorithm for combining a cityscape A of size n_1 and a cityscape B of size n_2 into one cityscape S of size O (n_1 + n_2). Your algorithm should run in time O (n_1 + n_2). Prove the correctness of your algorithm. Describe an O (n log n) time algorithm for finding the cityscape of n buildings. Prove the correctness of your algorithm and analyze its running time.

Explanation / Answer

a)

The running complexity would be O(n1+n2) as both the lists are iterated only once and their size is n1 and n2.

b)

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.