Queue Reconstruction by Height

1. Problem Description

Suppose a group of people in random order are standing in a queue. The array people represents the attributes of some people in the queue (not necessarily in order). Each people[i] = [hi, ki] means that the i-th person has height hi and there are exactly ki people in front whose height is greater than or equal to hi.

Reconstruct and return the queue represented by the input array people. The returned queue should be formatted as an array queue, where queue[j] = [hj, kj] is the attribute of the j-th person in the queue (queue[0] is the person at the front).

2. Approach

1. Approach 1
   • Sort first, then insert into the queue
   • For an array (a, b), first sort by a in descending order, then by b in ascending order

3. Implementation

3.1. Sorting

func reconstructQueue(people [][]int) [][]int {
    // Sort by height in descending order
    sort.Slice(people, func(i, j int) bool {
        a := people[i]
        b := people[j]
        return a[0] > b[0] || a[0] == b[0] && a[1] < b[1]
    })

    res := make([][]int, 0)
    for _, person := range people {
        res = insert(res, person[1], person)
    }
    return res

}

// Insert an element at index in the slice
func insert(people [][]int, index int, person []int) [][]int {
    current := [][]int{person}
    left := people[:index]
    right := people[index:]

    res := append(current, right...)
    res = append(left, res...)
    return res
}

4. References

• [Sort First, Then Insert] Animated Algorithm Walkthrough - Queue Reconstruction by Height - LeetCode