[leetcode] 253, 277, 279

253. Meeting Rooms II

https://leetcode.com/problems/meeting-rooms-ii/
https://www.lintcode.com/problem/919/

My Answer 1: Wrong Answer

"""
Definition of Interval.
class Interval(object):
    def __init__(self, start, end):
        self.start = start
        self.end = end
"""

class Solution:
    """
    @param intervals: an array of meeting time intervals
    @return: the minimum number of conference rooms required
    """
    def minMeetingRooms(self, intervals):
        intervals.sort(key= lambda v:(v.start, v.end))
        
        count = 1
        rooms = [[0, intervals[0].start], [intervals[0].end, float('inf')]]
        for i in range(1, len(intervals)):
            m = 0
            for j in range(len(rooms)):
                if rooms[j][0] <= intervals[i].start <= rooms[j][1] and intervals[i].end <= rooms[j][1]:
                    m = 1
                    if rooms[j][0] < intervals[i].start:
                        rooms.append([rooms[j][0], intervals[i].start])
                    if rooms[j][1] > intervals[i].end:
                        rooms.append([intervals[i].end, rooms[j][1]])
                    break
            if m == 0:
                count += 1
                rooms.append([-float('inf'), intervals[i].start])
                rooms.append([intervals[i].end, float('inf')])
        
        return count

1 <= intervals.length <= 10^4
0 <= start_i < end_i <= 10^6

To.린트코드
조건도 적어줬으면 좋겠어.
그럼 안녕..

우선 정렬부터 함

rooms 에 사용 가능한 시간대를 저장
intervals[0] 부터 선점하도록 초기화
ex) intervals = [(0,30), (5,10), (15,20)]
rooms => [[0 ~ 0], [30 ~ float('inf')]]

다음 시간대들을 보면서
rooms 에 포함되는 시간대가 있으면 그 룸에서 진행하면 되니까 count 는 그대로
대신 현재 시간대와 포함하는 시간대 사이의 간격들을 rooms 에 더 추가

rooms 에 포함되는 시간대가 없으면 원하는 시간에 룸이 없다는 거니까 새로 방파기
count + 1 & 새로운 방이니까 [0 ~ start], [end ~ float('inf')] 추가해서 사람 모집

근데 안됐읍니다...

Solution 1: Accepted (Runtime: 81 ms / Memory Usage: 5.92 MB) - 94.20 %

import heapq
class Solution:
    def minMeetingRooms(self, intervals):
        if not intervals:
            return 0
        intervals.sort(key= lambda v:(v.start, v.end))
        min_heap = [intervals[0].end] # stores only end_time
        
        for i in range(1, len(intervals)):
            if intervals[i].start < min_heap[0]:
                heapq.heappush(min_heap, intervals[i].end)
            else:
                heapq.heappushpop(min_heap, intervals[i].end)
        return len(min_heap)

Min-Heap 이용

우선 정렬을 해주고 min_heap 에 intervals[0].end 저장

for 문 돌려서
start 값이 min_heap[0] 보다 작으면 end 를 push
start 값이 min_heap[0] 보다 크거나 같으면 end 를 push 하고 제일 작은 값 pop

min_heap 길이 return

사실 잘 모르겠지만...
절 대 외 워 !!!!

---

277. Find the Celebrity

https://leetcode.com/problems/find-the-celebrity/
https://www.lintcode.com/problem/645/

My Answer 1: Accepted (Runtime: 922 ms / Memory Usage: 6.04 MB) - 37.40 %

"""
The knows API is already defined for you.
@param a, person a
@param b, person b
@return a boolean, whether a knows b
you can call Celebrity.knows(a, b)
"""


class Solution:
    # @param {int} n a party with n people
    # @return {int} the celebrity's label or -1
    def findCelebrity(self, n):
        # Write your code here
        for i in range(n):
            celeb1 = 1
            celeb2 = 1
            for j in range(n):
                if i != j and Celebrity.knows(i, j):
                    celeb1 = 0
                    break
                if i != j and Celebrity.knows(j, i) == 0:
                    celeb2 = 0
                    break
            if celeb1 and celeb2:
                return i
        
        return -1

셀럽 조건 1: 나는 누구도 알아봐선 안된다. 친목금지!!!
셀럽 조건 2: 남들은 모두 나를 알아봐야한다. 슈퍼스타!!!

두가지를 보면서 하나라도 만족하지 않으면 break 로 다음 사람 검사

둘 다 만족하는 사람이 진정한 💎👑🌟 Celebrity 🌟👑💎

---

279. Perfect Squares

https://leetcode.com/problems/perfect-squares/

My Answer 1: Accepted (Runtime: 5468 ms - 16.74% / Memory Usage: 14.3 MB - 71.70%)

class Solution:
    def numSquares(self, n: int) -> int:
        dp = [float('inf')]*(n+1)
        dp[0] = 0
        
        squares = []
        for i in range(1, n+1):
            if i**2 > n:
                break
            dp[i**2] = 1
            squares.append(i**2)
        
        for i in range(2, n+1):
            for j in range(len(squares)):
                if squares[j] <= i:
                    dp[i] = min(dp[i], dp[i-squares[j]] + 1)
                else:
                    break
            
        return dp[n]

n+1 크기의 dp를 만들어서 시스템 최댓값으로 초기화
dp[0] 은 사용하지 X => 0 처리

n 보다 작은 제곱수들을 구해서 squares 에 저장
이때 제곱수들은 dp 값도 1 로 처리

2 ~ n 까지 다시 보면서 최솟값으로 dp update
" 제곱수를 뺀 숫자의 dp 값 + 1 (= 제곱수 dp 값) " 비교
=> 1 ~ i-1 까지는 dp 값이 고정됐다는 점을 이용

ex) 12

num: 1 2 3 4 5 6 7 8 9 10 11 12
dp:  1 2 3 1 2 3 4 2 1 2  3  3

dp[12-1] + 1 = dp[11] + 1 = 3 + 1 = 4
dp[12-4] + 1 = dp[8] + 1 = 2 + 1 = 3
dp[12-9] + 1 = dp[3] + 1 = 3 + 1 = 4
중에 최솟값 3 을 갖게 됨

Solution 1: Accepted (Runtime: 4488 ms - 32.52% / Memory Usage: 14.3 MB - 83.32%)

class Solution:
    def numSquares(self, n: int) -> int:
        ## RC ##
        ## APPROACH : DP ##
        
		## TIME COMPLEXITY : O(N^2) ##
		## SPACE COMPLEXITY : O(N) ##
    
        if( n < 3) : return n
        square_nums = [i**2 for i in range(0, int(math.sqrt(n))+1)]
        
        dp = [float('inf')] * (n+1)
        dp[0] = 0
        for i in range(1, n+1):
            for square in square_nums:
                if(i < square): break
                dp[i] = min(dp[i], dp[i-square] + 1)    # +1 is for that square we are substracting.
        return dp[-1]

걍 똑같은데 더 깔끔하고 좀더 빠르다