มีเมทริกซ์แถวละ [height, count] count=คนหน้าที่สูงกว่าหรือเท่า คิวถูกสับ หาลำดับเดิม
เช่น [[2,2],[4,0],[5,0]] ให้ [[4,0],[5,0],[2,2]]
ขั้นตอนการแก้ปัญหา
- เรียงตาม height น้อยไปมาก, count มากไปน้อย
- สร้าง ans ขนาด N เติม None
- สำหรับแต่ละคน (h,c): หาตำแหน่งที่ว่างและมีคนสูงกว่า/เท่าอยู่หน้าพอดี c คน
ตัวอย่างโค้ด
class Solution:
def solve(self, matrix):
N = len(matrix)
matrix.sort(key=lambda x: [x[0], -x[1]])
ans = [None]*N
for h,c in matrix:
temp = 0
for i,num in enumerate(ans):
if temp >= c and num is None:
ans[i] = [h,c]; break
if num is None or num[0] >= h: temp += 1
return ans
ob = Solution()
matrix = [[2,2],[4,0],[5,0]]
print(ob.solve(matrix))
อินพุต
[[2,2],[4,0],[5,0]]
เอาต์พุต
[[4,0], [5,0], [2,2]]
