forked from TheAlgorithms/Java
-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathSkylineProblem.java
206 lines (180 loc) · 6.59 KB
/
SkylineProblem.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
package com.thealgorithms.others;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Scanner;
/**
* The {@code SkylineProblem} class is used to solve the skyline problem using a
* divide-and-conquer approach.
* It reads input for building data, processes it to find the skyline, and
* prints the skyline.
*/
public class SkylineProblem {
Building[] building;
int count;
/**
* Main function that reads input for the number of buildings and their
* dimensions, computes the skyline using divide-and-conquer,
* and prints the result.
*/
public void run() {
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
this.building = new Building[num];
// Read the building details and add them to the list of buildings
for (int i = 0; i < num; i++) {
String input = sc.next();
String[] data = input.split(",");
this.add(Integer.parseInt(data[0]), Integer.parseInt(data[1]), Integer.parseInt(data[2]));
}
this.print(this.findSkyline(0, num - 1));
sc.close();
}
/**
* Adds a building with the given left, height, and right values to the
* buildings list.
*
* @param left The left x-coordinate of the building.
* @param height The height of the building.
* @param right The right x-coordinate of the building.
*/
public void add(int left, int height, int right) {
building[count++] = new Building(left, height, right);
}
/**
* Prints the skyline as a sequence of coordinates and heights.
*
* @param skyline The list of {@link Skyline} objects representing the skyline.
*/
public void print(ArrayList<Skyline> skyline) {
Iterator<Skyline> it = skyline.iterator();
// Print each coordinate and height from the skyline list
while (it.hasNext()) {
Skyline temp = it.next();
System.out.print(temp.coordinates + "," + temp.height);
if (it.hasNext()) {
System.out.print(",");
}
}
}
/**
* Computes the skyline for a range of buildings using the divide-and-conquer
* approach.
*
* @param start The starting index of the buildings to process.
* @param end The ending index of the buildings to process.
* @return A list of {@link Skyline} objects representing the computed skyline.
*/
public ArrayList<Skyline> findSkyline(int start, int end) {
// Base case: only one building, return its skyline.
if (start == end) {
ArrayList<Skyline> list = new ArrayList<>();
list.add(new Skyline(building[start].left, building[start].height));
list.add(new Skyline(building[end].right, 0)); // Add the end of the building
return list;
}
int mid = (start + end) / 2;
ArrayList<Skyline> sky1 = this.findSkyline(start, mid); // Find the skyline of the left half
ArrayList<Skyline> sky2 = this.findSkyline(mid + 1, end); // Find the skyline of the right half
return this.mergeSkyline(sky1, sky2); // Merge the two skylines
}
/**
* Merges two skylines (sky1 and sky2) into one combined skyline.
*
* @param sky1 The first skyline list.
* @param sky2 The second skyline list.
* @return A list of {@link Skyline} objects representing the merged skyline.
*/
public ArrayList<Skyline> mergeSkyline(ArrayList<Skyline> sky1, ArrayList<Skyline> sky2) {
int currentH1 = 0;
int currentH2 = 0;
ArrayList<Skyline> skyline = new ArrayList<>();
int maxH = 0;
// Merge the two skylines
while (!sky1.isEmpty() && !sky2.isEmpty()) {
if (sky1.get(0).coordinates < sky2.get(0).coordinates) {
int currentX = sky1.get(0).coordinates;
currentH1 = sky1.get(0).height;
if (currentH1 < currentH2) {
sky1.remove(0);
if (maxH != currentH2) {
skyline.add(new Skyline(currentX, currentH2));
}
} else {
maxH = currentH1;
sky1.remove(0);
skyline.add(new Skyline(currentX, currentH1));
}
} else {
int currentX = sky2.get(0).coordinates;
currentH2 = sky2.get(0).height;
if (currentH2 < currentH1) {
sky2.remove(0);
if (maxH != currentH1) {
skyline.add(new Skyline(currentX, currentH1));
}
} else {
maxH = currentH2;
sky2.remove(0);
skyline.add(new Skyline(currentX, currentH2));
}
}
}
// Add any remaining points from sky1 or sky2
while (!sky1.isEmpty()) {
skyline.add(sky1.get(0));
sky1.remove(0);
}
while (!sky2.isEmpty()) {
skyline.add(sky2.get(0));
sky2.remove(0);
}
return skyline;
}
/**
* A class representing a point in the skyline with its x-coordinate and height.
*/
public class Skyline {
public int coordinates;
public int height;
/**
* Constructor for the {@code Skyline} class.
*
* @param coordinates The x-coordinate of the skyline point.
* @param height The height of the skyline at the given coordinate.
*/
public Skyline(int coordinates, int height) {
this.coordinates = coordinates;
this.height = height;
}
}
/**
* A class representing a building with its left, height, and right
* x-coordinates.
*/
public class Building {
public int left;
public int height;
public int right;
/**
* Constructor for the {@code Building} class.
*
* @param left The left x-coordinate of the building.
* @param height The height of the building.
* @param right The right x-coordinate of the building.
*/
public Building(int left, int height, int right) {
this.left = left;
this.height = height;
this.right = right;
}
}
/**
* The main method that runs the skyline problem solution.
*
* @param args Command-line arguments (not used).
*/
public static void main(String[] args) {
SkylineProblem skylineProblem = new SkylineProblem();
skylineProblem.run();
}
}