Silhuettproblemet

Silhuettproblemet - lösning

Strategi

  • Gå igenom kursens algoritmer. Finns det något liknande?

    Max-beräkning - vilken av byggnaderna är högst på denna x-koordinat? Måste göras upprepade gånger.

  • Gå igenom kursens datastrukturer. Finns någon lämplig?

    En max-heap kan användas för att hitta högsta byggnaden.

  • Hur hålla reda på vilka byggnader som är aktuella för en viss position?

    En min-heap kan användas för att hålla reda på vilka hus som är aktuella.

Lösning

Datastrukturer: Det här problemet kan vi lösa med hjälp av två heapar.

  • Den ena är en min-heap, som ser till att vi får ut husväggarnas koordinater i ordning från minsta (vänstraste) till största (högraste) x-värde. Där är prioriteten husets x-koordinat.
  • Den andra är en max-heap som hjälper oss att hitta det just nu högsta huset. Där är prioriteten husets höjd.

Algoritm:

  1. Lägg in alla hus, med vänstervägg som nyckel, i en min-heap som vi kallar xheap.
  2. Skapa också en tom max-heap, som vi kallar för yheap, där vi (så småningom) ska sortera husen efter höjd.
  3. Låt x och y vara aktuell x-koordinat resp y-koordinat. Båda är noll från början.
  4. Så länge det finns hus kvar i xheap,
    1. Ta ut första huset ur xheap (vi får det hus som har den vänstraste vänsterväggen).
    2. Om vänsterväggen ligger efter aktuell x-koordinat...
      • ...så blir den ny x-koordinat.
      • Om dessutom huset höjd är högre än aktuell y-koordinat skriver vi ut x och y.
      • Stoppa in huset i xheap igen, men nu med högerväggen som nyckel.
      • Stoppa in samma hus i yheap med höjden som nyckel.
    3. men om vänsterväggen inte ligger efter aktuell x-koordinat har vi fått ut ett hus med högervägg som nyckel, och då...
      • ...letar vi igenom yheap efter det högsta huset vars högervägg inte ligger efter aktuell x-koordinat.
      • Om yheap tar slut medan vi letar är höjden noll.
      • Sen skriver vi ut x och y.

Tidskomplexitet:

  • Vilken variabel (eller vilka variabler) beror tidskomplexiteten av i detta problem?

         Indata är husens koordinater. Indatas storlek n = antal hus

  • Hur många operationer utförs i varje steg i algoritmen?
    • Lägg in alla hus i xheap: n*logn
    • Varje hus i xheap plockas ut, och stoppas in igen (med annan nyckel): n*logn
    • Varje hus stoppas in i yheap: n*logn

        Totalt O(n*logn)

 

Programkod

from maxheap import MaxHeap
from minheap import MinHeap

class House:

    def __init__(self, left = None, height = None, right = None):
        self.left = left
        self.height = height
        self.right = right

    def __str__(self):
        return f"({self.left},{self.height},{self.right})"

def readHouses():
    """Läs in husen"""
    xheap = MinHeap()
    ins = input("Vilka hus finns? ").split()
    for h in ins:
        h = h.strip("()")
        hs = h.split(",")
        house = House(int(hs[0]), int(hs[1]), int(hs[2]))
        xheap.put(house, house.left)
    return xheap

def main():
    yheap = MaxHeap()
    xheap = readHouses()
    x = 0
    y = 0
    while not xheap.isEmpty():
        house = xheap.get()
        if house.left > x:  # Hus med vänstervägg utplockat
            x = house.left
            if house.height > y:
                y = house.height
                print(f"({x},{y})", end = "")
            xheap.put(House(house.left, house.height, house.right), house.right)
            yheap.put(House(house.left, house.height, house.right), house.height)

        else: # Hus med högervägg utplockat
            if house.height == y: # Det var det just nu högsta huset
                # Sök efter det hus som blir högst nu
                x = house.right
                while not yheap.isEmpty() and (yheap.top().right <= x):
                    yheap.get()     # Ta bort hus som ligger till vänster om x
                if yheap.isEmpty():
                    y = 0
                else:
                    y = yheap.top().height
                print(f"({x},{y})", end = "")

main()

Kattis

Programmet är godkänt i Kattis, se https://kth.kattis.com/submissions/298571 Links to an external site.


Testkörningar

Enkelt exempel med separata hus:

Vilka hus finns? (1,2,3) (2,4,5)
(1,2)(2,4)(5,0)

Högt brett hus som täcker alla hus inuti:

Vilka hus finns? (1,4,10) (3,2,4) (5,2,6) (7,2,8)
(1,4)(10,0)

Lågt brett hus som låter de inre husen sticka upp :

Vilka hus finns? (1,2,10) (3,4,4) (5,4,6) (7,4,8)
(1,2)(3,4)(4,2)(5,4)(6,2)(7,4)(8,2)(10,0)