InterviewQuestions/CityTrace.cpp at master · drewc71/InterviewQuestions · 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

// Question: Given a description of buildings, trace the outline of the resulting city

/*
    Input buildings (left, right) : height  [sorted by left]
        (2, 12) : 8
        (9, 13) : 5
        (15, 29) : 2
        (20, 29) : 4
        (23, 28) : 8

    X-ray plot:

    9 ..............................
    8 ..┌─────────┐..........┌────┐.
    7 ..│.........│..........│....│.
    6 ..│.........│..........│....│.
    5 ..│......┌──┼┐.........│....│.
    4 ..│......│..││......┌──┼────┼┐
    3 ..│......│..││......│..│....││
    2 ..│......│..││.┌────┼──┼────┼┤
    1 ..│......│..││.│....│..│....││
    0 ──┴──────┴──┴┴─┴────┴──┴────┴┴
                1         2
      012345678901234567890123456789

    Skyline plot:

    9 ..............................
    8 ..┌─────────┐..........┌────┐.
    7 ..│.........│..........│....│.
    6 ..│.........│..........│....│.
    5 ..│.........└┐.........│....│.
    4 ..│..........│......┌──┘....└┐
    3 ..│..........│......│........│
    2 ..│..........│.┌────┘........│
    1 ..│..........│.│.............│
    0 ──┴──────────┴─┴─────────────┴
                1         2
      012345678901234567890123456789

    Output segments (runTo, newHeight)  [sorted by runTo]
        (2, 8)
        (12, 5)
        (13, 0)
        (15, 2)
        (20, 4)
        (23, 8)
        (28, 4)
        (29, 0)
*/