파이썬에서 다른 상자 안에 들어갈 수 있는 최대 상자 수를 찾는 프로그램

각 행이 주어진 상자의 높이와 너비를 나타내는 상자 목록이 있다고 가정합니다. 첫 번째 상자가 두 번째 상자보다 작으면 다른 상자에 상자를 넣을 수 있습니다(너비와 높이가 모두 다른 상자보다 작을 때). 상자에 넣을 수 있는 최대 상자 수를 찾아야 합니다.

따라서 입력이 다음과 같으면

그러면 [12, 12] 상자에 넣을 수 있는 [10, 10] 안에 상자 [6, 6]을 맞출 수 있으므로 출력은 3이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• insert_index() 함수를 정의합니다. 시간이 걸립니다. this_h
• l :=0
• r :=arr의 크기 - 1
• res :=0
• l <=r인 동안, do
  • m :=l +(r - l) // 2
  • cur_h :=arr[m]
  • cur_h
  • res :=m
  • l :=m + 1
• 그렇지 않으면
  • r :=m - 1

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

class Solution:
   def solve(self, matrix):
      matrix = sorted(matrix, key=lambda x: (x[0], -x[1]))
      n = len(matrix)

      heights = [float("inf")] * (n + 1)
      heights[0] = float("-inf")
      res = 0

      for box in matrix:
         cur_w, cur_h = box
         index = self.insert_index(heights, cur_h)

         if heights[index] >= cur_h:
            heights[index] = cur_h
         res = max(res, index)
      return res

   def insert_index(self, arr, this_h):
      l = 0
      r = len(arr) - 1
      res = 0
      while l <= r:
         m = l + (r - l) // 2
         cur_h = arr[m]
         if cur_h < this_h:
            res = m
            l = m + 1
         else:
            r = m - 1
      return res + 1

ob = Solution()
matrix = [
   [12, 12],
   [10, 10],
   [6, 6],
   [5, 10]
]
print(ob.solve(matrix))

입력

matrix = [  
[12, 12],  
[10, 10],  
[6, 6],  
[5, 10] ]

출력

3