Accepted Golang solution, no priority queue or heap involed


  • 0
    F

    In a linked list (it;s empty at first), each building can be considered as a range, and these ranges can overlap each other if one's height is higher than others'.
    one by one put the building/range into the linked list, at last, we get whole linked list which essentially is the skyline.
    the complexity should be O(n*n)

    type Range struct {
    	a, b, h int
    	Next    *Range
    }
    
    func put(p, one *Range) *Range {
    	if p == nil {
    		return one
    	}
    	if one.a >= one.b {
    		//zero range
    		return p
    	}
    	//does not overlap
    	if one.a > p.b {
    		p.Next = put(p.Next, one)
    		return p
    	}
    	//overlap
    	if p.h >= one.h { //overlap but not overwrite
    		one.a = p.b
    		p.Next = put(p.Next, one)
    	} else { //one will overwrite current range
    		if one.b < p.b {
    			one.Next = &Range{one.b, p.b, p.h, p.Next}
    			p.b = one.a
    			p.Next = one
    		} else {
    			one2 := &Range{p.b, one.b, one.h, nil}
    			one.Next = p.Next
    			p.Next = one
    			one.b = p.b
    			p.b = one.a
    			one.Next = put(one.Next, one2)
    		}
    	}
    	// remove empty range as many as possible
    	for ; p != nil && p.a >= p.b; p = p.Next {
    	}
    	return p
    }
    
    func getSkyline(buildings [][]int) [][]int {
    	if len(buildings) == 0 {
    		return [][]int{}
    	}
    	var root *Range = nil
    	for _, a := range buildings {
    		root = put(root, &Range{a[0], a[1], a[2], nil})
    	}
    	ret := make([][]int, 0, len(buildings))
    	last_pos := 0
    	for p := root; p != nil; p = p.Next {
    		// remove the empty range
    		if p.a >= p.b {
    			continue
    		}
    		//fmt.Printf("%d -> %d : %d\n", p.a, p.b, p.h)
    		if len(ret) < 1 { // init the first one
    			ret = append(ret, []int{p.a, p.h})
    			last_pos = p.b
    			continue
    		}
    		// deal with the gap between two buildings
    		if p.a > last_pos {
    			ret = append(ret, []int{last_pos, 0})
    		}
    		// deal with continuous range
    		last_range := ret[len(ret)-1]
    		if p.h != last_range[1] {
    			ret = append(ret, []int{p.a, p.h})
    		}
    		last_pos = p.b
    	}
    	ret = append(ret, []int{last_pos, 0})
    	return ret
    }
    
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.