You are designing background art for a video game in the for

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 0 (n_1 + n_2). Your algorithm should run in time 0 (n_1 + n_2). Prove the correctness of your algorithm. Describe an 0 {n log n) time algorithm for finding the cityscape of n buildings. Prove the correctness of your algorithm and analyze its running time.

Solution

In Order to Combine a City Scape A and City Scape B,

We will use the idea of Merge Procedure that is used in a Merge Sort:-

1. Start from the first strip of two CityScapes , compare the x coordinates.
2. Pick the strip with smaller x coordinate and add it to our result.
3. The height of added strip is considered as maximum of current heights from CityScape A and CityScape B

We will go over the example to Prove it :-

CityScape A = {(1,11) , (3,13) , (9,0) , ( 12,7) , (16,0)}
CityScape B = {(14,3) , (19,18) , (22,3) , ( 23,13) , (29,0)}
Resultant = {};
Ha = 0 , Hb = 0
Take two index i and j pointing to start elements of two CityScape
Step-1 : Pick (1,11) and (14,3) Compare x coordinate , Add smaller i.e (1,11) to our list and height becomes max(11,0) so Ha = 11 and Resultant = {(1,11)};
Increment the first index i .

Step-2 : Pick (3,13) and (14,3) Compare x coordinate , Add smaller i.e (3,13) to our list and height becomes max(13,0) so Ha = 13 and Resultant = {(1,11) , (3,13)};
Increment the first index i .

Step-3 : Pick (9,0) and (14,3) Compare x coordinate , Add smaller i.e (9,0) to our list and height becomes max(9,0) so H = 9 and Resultant = {(1,11) , (3,13) , (9,0)};
Increment the first index i .

Step-4 : Pick (12,7) and (14,3) Compare x coordinate , Add smaller i.e (12,7) to our list and height becomes max(7,0) so H = 7 and Resultant = {(1,11) , (3,13) , (9,0) , (12,7)};
Increment the first index i .

Step-5 : Pick (16,0) and (14,3) Compare x coordinate , Add smaller i.e (14,3) to our list and height becomes max(3,7) so H = 7 and Haand Resultant = {(1,11) , (3,13) , (9,0) , (12,7) , (14,3)};
Increment the second index j.

Step-6 : Pick (16,0) and (19,18) Compare x coordinate , Add smaller i.e (16,0) to our list and height becomes max(0,3) so H = 3 and Haand Resultant = {(1,11) , (3,13) , (9,0) , (12,7) , (14,3) , (16,3) . . . .. . .etc};
Increment the second index j.

In this way we keep incrementing i and j , So total time complexity is O(n1 + n2)




B) Given a Building {{1, 11, 5}, {2, 6, 7}, {3, 13, 9} {12, 7, 16} . . . .. etc .. . . .. . } ,
Starting from 0 till the length . We will use Divide and Conquer paradign to solve the problem.

We find mid and Divide the CityScape into two parts A and B


So Idea is to divide the Problem into Two Subproblems and try to solve them recursively .
So its Like

mid = low + high /2 ;
findCityScape(Building, low, mid);
findCityScape(Building, mid+1, high)
Merge(ptr) //Described in Part A


At the end we get the City Scape of N Building.

So If we try to analyze the time complexity it will be :

T(N) : Time taken for N buildings
T(N) = 2T(N/2) + N

If we solve this recurrance we will get T(N) = O(N log N)

Thanks, let me know if there is any concern.

So In this way