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

// @Title: 根据身高重建队列 (Queue Reconstruction by Height)
// @Author: 15816537946@163.com
// @Date: 2019-11-17 17:18:37
// @Runtime: 16 ms
// @Memory: 5.9 MB
/*
 * @lc app=leetcode.cn id=406 lang=golang
 *
 * [406] 根据身高重建队列
 *
 * https://leetcode-cn.com/problems/queue-reconstruction-by-height/description/
 *
 * algorithms
 * Medium (62.35%)
 * Likes:    144
 * Dislikes: 0
 * Total Accepted:    6.3K
 * Total Submissions: 10.1K
 * Testcase Example:  '[[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]'
 *
 * 假设有打乱顺序的一群人站成一个队列。 每个人由一个整数对(h, k)表示，其中h是这个人的身高，k是排在这个人前面且身高大于或等于h的人数。
 * 编写一个算法来重建这个队列。
 * 
 * 注意：
 * 总人数少于1100人。
 * 
 * 示例
 * 
 * 
 * 输入:
 * [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
 * 
 * 输出:
 * [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]
 * 
 * 
 */
 /*
func reconstructQueue(people [][]int) [][]int {
	if len(people) <=1 {
		return people
	}

	fmt.Println("before ->", people)
	sort.Sort(persons(people))
	fmt.Println("after ->", people)

	res := make([][]int, 0, len(people))
	// 插入函数，把person插入到res[idx]上
	insert := func(idx int, person []int) {
		res = append(res, []int{})
		copy(res[idx+1:], res[idx:])
		res[idx] = person
	}

	for _, v := range people {
		insert(v[1], v)
	}
	fmt.Println(res)
	return res
}

type persons [][]int

func (p persons) Len() int { return len(p)}

// h降序，k升序
func (p persons) Less(i,j int) bool {
	if p[i][0] == p[j][0] {
		return p[i][1] < p[j][1]
	}
	return p[i][0] > p[j][0]
}

func (p persons) Swap(i, j int) { p[i], p[j] = p[j], p[i]}
*/
func reconstructQueue(people [][]int) [][]int {
	if len(people) <= 1 {
		return people
	}

	sort.Sort((persons(people)))

	ret := make([][]int, 0)
	insert := func(idx  int, person []int) {
		ret = append(ret, []int{})
		copy(ret[idx+1:], ret[idx:])
		ret[idx] = person
	}

	for _, v := range people {
		insert(v[1], v)
	}

	return ret

}

type persons [][]int

func (p persons) Len() int { return len(p) }

func (p persons) Less(i, j int) bool {
	if p[i][0] == p[j][0] {
		return p[i][1] < p[j][1]
	}
	return p[i][0] > p[j][0]
}

func (p persons) Swap(i, j int) { p[i], p[j] = p[j], p[i] }