interview-problems/skyline.java at main · arvindpruthi/interview-problems · GitHub

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
import java.util.TreeMap;
import java.util.Map;
import java.util.List;
import java.util.ArrayList;

class skyline {


    // This is an intervals problem. We have to convert this data into a series of intervals with max height.
    static class interval implements Comparable<interval> {
        int x1;
        int x2;
        interval(int x1, int x2) {
            this.x1 = x1;
            this.x2 = x2;
        }

        @Override
        public int compareTo(interval to) {
            if (x1 < to.x1)
                return -1;
            if (x1 > to.x1)
                return 1;
            if (x2 < to.x2)
                return -1;
            if (x2 > to.x2)
                return 1;
            return 0;
        }
    }

    static class coord {
        int x;
        int y;
        public coord(int x, int y) {
            this.x = x;
            this.y = y;
        }
        public void printCoord() {
            System.out.println("(" + x + ", " + y + ")");
        }
    }


    public static List<coord> easyCalc(int[][] buildings) {
        List<coord> coordlist = new ArrayList<>();

        // determine max coordinates from the buildings array
        int maxXCoord = 0;
        for (int i=0; i<buildings.length; i++) {
            if (buildings[i][1] > maxXCoord)
                maxXCoord = buildings[i][1];
        }
        int[] htMap = new int[maxXCoord+2];

        for (int i=0; i<buildings.length; i++) {
            for (int j=buildings[i][0]; j<buildings[i][1]; j++) {
                int y = buildings[i][2];
                if (y > htMap[j])
                    htMap[j] = y;
            }
        }

        int prevHt = 0;
        for (int i=0; i<=maxXCoord+1; i++) {
            Integer xcoord = i;
            Integer ycoord = htMap[i];
            if (ycoord != prevHt) {
                coordlist.add(new coord(xcoord, ycoord));
                prevHt = ycoord;
            }
        }

        return coordlist;
    }

    public static List<coord> intervalMethod(int[][] buildings) {
        List<coord> coordlist = new ArrayList<>();
        Map<interval, Integer> intervalMap = new TreeMap<>();
        Map<interval, Integer> processedMap = new TreeMap<>();
        for (int i=0; i<buildings.length; i++) {
            intervalMap.put(new interval(buildings[i][0], buildings[i][1]), buildings[i][2]);
        }

        interval prevInterval = null;
        int prevHt = 0;
        for (interval current : intervalMap.keySet()) {
            int ht = intervalMap.get(current);
            if (prevInterval != null) {
                // Check for overlap
                if (prevInterval.x2 >= current.x1) {
                    if (ht > prevHt) {
                        // We have overlapping intervals & current Ht is greater than the previous ht, then cut the prev interval shorter
                        processedMap.remove(prevInterval);
                        prevInterval.x2 = current.x1;
                        // reinsert
                        processedMap.put(prevInterval, prevHt);
                    } else if (prevHt > ht) {
                        // cut short the current interval
                        current.x1 = prevInterval.x2;

                    }
                }
            }
            processedMap.put(current, ht);
            prevInterval = current;
            prevHt = ht;
        }

        prevInterval = null;
        prevHt = 0;
        for (interval current : processedMap.keySet()) {
            int ht = intervalMap.get(current);
            if (prevInterval != null) {
                if (prevInterval.x2 < current.x1) {
                    // first introduce a 0
                    coordlist.add(new coord(prevInterval.x2, 0));
                }
            }
            coordlist.add(new coord(current.x1, ht));
            prevHt = ht;
            prevInterval = current;
        }
        coordlist.add(new coord(prevInterval.x2, 0));
        return coordlist;
    }
    public static void main(String[] args) {
        int[][] buildings = {
            {2,9,10},
            {3,7,15},
            {5,12,12},
            {15,20,10},
            {19,24,8}
        };

        List<coord> coordList = skyline.easyCalc(buildings);

        System.out.println("Calculated coordinates for the silhouette are: ");
        for (coord entry : coordList) {
            entry.printCoord();
        }

        coordList = skyline.intervalMethod(buildings);
        System.out.println("Calculated coordinates for the silhouette using the interval method are: ");
        for (coord entry : coordList) {
            entry.printCoord();
        }
    }
}