Skip to content

Commit 2029156

Browse files
author
Christian Bender
authored
Merge pull request TheAlgorithms#311 from sangjun2/master
implement SkylineProblem
2 parents 55c3aac + a8e0a48 commit 2029156

File tree

2 files changed

+262
-0
lines changed

2 files changed

+262
-0
lines changed

‎Others/SkylineProblem.java

Lines changed: 131 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,131 @@
1+
import java.util.ArrayList;
2+
import java.util.Iterator;
3+
import java.util.Scanner;
4+
5+
public class SkylineProblem {
6+
Building[] building;
7+
int count;
8+
9+
public void run() {
10+
Scanner sc = new Scanner(System.in);
11+
12+
int num = sc.nextInt();
13+
this.building = new Building[num];
14+
15+
for(int i = 0; i < num; i++) {
16+
String input = sc.next();
17+
String[] data = input.split(",");
18+
this.add(Integer.parseInt(data[0]), Integer.parseInt(data[1]), Integer.parseInt(data[2]));
19+
}
20+
this.print(this.findSkyline(0, num - 1));
21+
22+
sc.close();
23+
}
24+
25+
public void add(int left, int height, int right) {
26+
building[count++] = new Building(left, height, right);
27+
}
28+
29+
public void print(ArrayList<Skyline> skyline) {
30+
Iterator<Skyline> it = skyline.iterator();
31+
32+
while(it.hasNext()) {
33+
Skyline temp = it.next();
34+
System.out.print(temp.coordinates + "," + temp.height);
35+
if(it.hasNext()) {
36+
System.out.print(",");
37+
}
38+
}
39+
40+
}
41+
42+
public ArrayList<Skyline> findSkyline(int start, int end) {
43+
if(start == end) {
44+
ArrayList<Skyline> list = new ArrayList<>();
45+
list.add(new Skyline(building[start].left, building[start].height));
46+
list.add(new Skyline(building[end].right, 0));
47+
48+
return list;
49+
}
50+
51+
int mid = (start + end) / 2;
52+
53+
ArrayList<Skyline> sky1 = this.findSkyline(start, mid);
54+
ArrayList<Skyline> sky2 = this.findSkyline(mid + 1, end);
55+
56+
return this.mergeSkyline(sky1, sky2);
57+
}
58+
59+
public ArrayList<Skyline> mergeSkyline(ArrayList<Skyline> sky1, ArrayList<Skyline> sky2) {
60+
int currentH1 = 0, currentH2 = 0;
61+
ArrayList<Skyline> skyline = new ArrayList<>();
62+
int maxH = 0;
63+
64+
while(!sky1.isEmpty() && !sky2.isEmpty()) {
65+
if(sky1.get(0).coordinates < sky2.get(0).coordinates) {
66+
int currentX = sky1.get(0).coordinates;
67+
currentH1 = sky1.get(0).height;
68+
69+
if(currentH1 < currentH2) {
70+
sky1.remove(0);
71+
if(maxH != currentH2) skyline.add(new Skyline(currentX, currentH2));
72+
} else {
73+
maxH = currentH1;
74+
sky1.remove(0);
75+
skyline.add(new Skyline(currentX, currentH1));
76+
}
77+
} else {
78+
int currentX = sky2.get(0).coordinates;
79+
currentH2 = sky2.get(0).height;
80+
81+
if(currentH2 < currentH1) {
82+
sky2.remove(0);
83+
if(maxH != currentH1) skyline.add(new Skyline(currentX, currentH1));
84+
} else {
85+
maxH = currentH2;
86+
sky2.remove(0);
87+
skyline.add(new Skyline(currentX, currentH2));
88+
}
89+
}
90+
}
91+
92+
while(!sky1.isEmpty()) {
93+
skyline.add(sky1.get(0));
94+
sky1.remove(0);
95+
}
96+
97+
while(!sky2.isEmpty()) {
98+
skyline.add(sky2.get(0));
99+
sky2.remove(0);
100+
}
101+
102+
return skyline;
103+
}
104+
105+
public class Skyline {
106+
public int coordinates;
107+
public int height;
108+
109+
public Skyline(int coordinates, int height) {
110+
this.coordinates = coordinates;
111+
this.height = height;
112+
}
113+
}
114+
115+
public class Building {
116+
public int left;
117+
public int height;
118+
public int right;
119+
120+
public Building(int left, int height, int right) {
121+
this.left = left;
122+
this.height = height;
123+
this.right = right;
124+
}
125+
}
126+
127+
public static void main(String[] args) {
128+
SkylineProblem skylineProblem = new SkylineProblem();
129+
skylineProblem.run();
130+
}
131+
}

‎SkylineProblem/SkylineProblem.java

Lines changed: 131 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,131 @@
1+
import java.util.ArrayList;
2+
import java.util.Iterator;
3+
import java.util.Scanner;
4+
5+
public class SkylineProblem {
6+
Building[] building;
7+
int count;
8+
9+
public void run() {
10+
Scanner sc = new Scanner(System.in);
11+
12+
int num = sc.nextInt();
13+
this.building = new Building[num];
14+
15+
for(int i = 0; i < num; i++) {
16+
String input = sc.next();
17+
String[] data = input.split(",");
18+
this.add(Integer.parseInt(data[0]), Integer.parseInt(data[1]), Integer.parseInt(data[2]));
19+
}
20+
this.print(this.findSkyline(0, num - 1));
21+
22+
sc.close();
23+
}
24+
25+
public void add(int left, int height, int right) {
26+
building[count++] = new Building(left, height, right);
27+
}
28+
29+
public void print(ArrayList<Skyline> skyline) {
30+
Iterator<Skyline> it = skyline.iterator();
31+
32+
while(it.hasNext()) {
33+
Skyline temp = it.next();
34+
System.out.print(temp.coordinates + "," + temp.height);
35+
if(it.hasNext()) {
36+
System.out.print(",");
37+
}
38+
}
39+
40+
}
41+
42+
public ArrayList<Skyline> findSkyline(int start, int end) {
43+
if(start == end) {
44+
ArrayList<Skyline> list = new ArrayList<>();
45+
list.add(new Skyline(building[start].left, building[start].height));
46+
list.add(new Skyline(building[end].right, 0));
47+
48+
return list;
49+
}
50+
51+
int mid = (start + end) / 2;
52+
53+
ArrayList<Skyline> sky1 = this.findSkyline(start, mid);
54+
ArrayList<Skyline> sky2 = this.findSkyline(mid + 1, end);
55+
56+
return this.mergeSkyline(sky1, sky2);
57+
}
58+
59+
public ArrayList<Skyline> mergeSkyline(ArrayList<Skyline> sky1, ArrayList<Skyline> sky2) {
60+
int currentH1 = 0, currentH2 = 0;
61+
ArrayList<Skyline> skyline = new ArrayList<>();
62+
int maxH = 0;
63+
64+
while(!sky1.isEmpty() && !sky2.isEmpty()) {
65+
if(sky1.get(0).coordinates < sky2.get(0).coordinates) {
66+
int currentX = sky1.get(0).coordinates;
67+
currentH1 = sky1.get(0).height;
68+
69+
if(currentH1 < currentH2) {
70+
sky1.remove(0);
71+
if(maxH != currentH2) skyline.add(new Skyline(currentX, currentH2));
72+
} else {
73+
maxH = currentH1;
74+
sky1.remove(0);
75+
skyline.add(new Skyline(currentX, currentH1));
76+
}
77+
} else {
78+
int currentX = sky2.get(0).coordinates;
79+
currentH2 = sky2.get(0).height;
80+
81+
if(currentH2 < currentH1) {
82+
sky2.remove(0);
83+
if(maxH != currentH1) skyline.add(new Skyline(currentX, currentH1));
84+
} else {
85+
maxH = currentH2;
86+
sky2.remove(0);
87+
skyline.add(new Skyline(currentX, currentH2));
88+
}
89+
}
90+
}
91+
92+
while(!sky1.isEmpty()) {
93+
skyline.add(sky1.get(0));
94+
sky1.remove(0);
95+
}
96+
97+
while(!sky2.isEmpty()) {
98+
skyline.add(sky2.get(0));
99+
sky2.remove(0);
100+
}
101+
102+
return skyline;
103+
}
104+
105+
public class Skyline {
106+
public int coordinates;
107+
public int height;
108+
109+
public Skyline(int coordinates, int height) {
110+
this.coordinates = coordinates;
111+
this.height = height;
112+
}
113+
}
114+
115+
public class Building {
116+
public int left;
117+
public int height;
118+
public int right;
119+
120+
public Building(int left, int height, int right) {
121+
this.left = left;
122+
this.height = height;
123+
this.right = right;
124+
}
125+
}
126+
127+
public static void main(String[] args) {
128+
SkylineProblem skylineProblem = new SkylineProblem();
129+
skylineProblem.run();
130+
}
131+
}

0 commit comments

Comments
 (0)