[LeetCode]Daily Challenge: Boats to Save People (Python)

LeetCode - Daily Challenge - Boats to Save People

Problem Description

The i-th person has weight people[i], and each boat can carry a maximum weight of limit.

Each boat carries at most 2 people at the same time, provided the sum of the weight of those people is at the most limit.

 

Return the minimum number of boats to carry every given person.

(It is guaranteed each person can be carried by boat.) 

 

Example 1:

• Input: people = [1,2], limit = 3
• Output: 1
• Explanation: 1 boat (1, 2)

Example 2:

• Input: people = [3,2,2,1], limit = 3
• Output: 3
• Explanation: 3 boats (1, 2), (2) and (3)

Example 3:

• Input: people = [3,5,3,4], limit = 5
• Output: 4
• Explanation: 4 boats (3), (3), (4), (5)

Constraints:

• 1 <= people.length <= 50000
• 1 <= people[i] <= limit <= 30000

My Solution (Python)

class Solution(object):
    def numRescueBoats(self, people, limit):
        """
        :type people: List[int]
        :type limit: int
        :rtype: int
        """
        answer = 0
        heaviest = len(people) -1
        lightest = 0
        people.sort()

        while heaviest >= lightest:
            if people[heaviest] + people[lightest] <= limit:
                lightest += 1
            heaviest -= 1
            answer += 1
        
        return answer

최대 2명이 탑승할 수 있는 보트의 무게 제한 수는 limit, 각 사람들의 무게는 people 리스트로 제공된다.

즉, 가장 무거운 사람과 가벼운 사람을 더한 뒤 limit보다 작거나 같은지 확인 한 후 태우면 된다.

1. people 리스트를 정렬한다.
2. 가장 무거운 사람의 index number를 heaviest에 저장, 가장 가벼운 사람의 index number를 lightest에 저장한다.
3. 반복문:
   1. 가장 무거운 사람과 가벼운 사람을 더한 값이 limit보다 작으면 둘 다 보트에 태우므로 lightest++, heaviest--, answer++
   2. limit보다 크면 무거운 사람만 보트에 태울 수 있으므로 heaviest--, answer++
   3. index number가 옳지 않으면 (heaviest가 lightest보다 적으면 가장 무거운 사람이 가장 가벼운 사람이 되어버린다.) 반복문을 빠져나온다. 
4. answer를 리턴한다.