[Mock] Apple 6

911. Online Election

In an election, the i-th vote was cast for persons[i] at time times[i].

Now, we would like to implement the following query function: TopVotedCandidate.q(int t) will return the number of the person that was leading the election at time t.

Votes cast at time t will count towards our query. In the case of a tie, the most recent vote (among tied candidates) wins.

My Answer 1: Accepted (Runtime: 2212 ms - 8.78% / Memory Usage: 19.2 MB - 96.03%)

class TopVotedCandidate:

    def __init__(self, persons: List[int], times: List[int]):
        self.winner = [0] * len(times)    ## 시간별 winner
        candidate = [0] * len(persons)    ## 후보자별 득표수
        same = 0			  ## 동점 中 가장 최근에 득표한 person
        maxvote = 0			  ## 최다 득표수
        for i in range(len(persons)):
            candidate[persons[i]] += 1	  ## 득표수 집계
            ## 새로운 winner 탄생~ => maxvote update
            if maxvote < candidate[persons[i]]:
                maxvote = candidate[persons[i]]
                
            ## 동점 中 winner 도 update
            if maxvote == candidate[persons[i]]:
                self.winner[i] = persons[i]
                same = persons[i]
            else:
                ## 최다 득표수를 가진 동점자가 여러명일 때
                if candidate.count(maxvote) > 1:
                    self.winner[i] = same
                ## 나머지는 최다 득표수의 후보자를 넣어주기
                else:
                    self.winner[i] = candidate.index(maxvote)
        ## times 는 그대로 복사
        self.times = times

    def q(self, t: int) -> int:
        ## Binary Search 로 t 의 위치 찾기
        l = 0 
        r = len(self.times)-1

        while l <= r:
            m = (l+r) // 2
            
            if self.times[m] == t:
                l = m
                break
            elif self.times[m] > t:
                r = m - 1
            else:
                l = m + 1
        
        if l > r:
            return self.winner[r]
            
        return self.winner[l]


# Your TopVotedCandidate object will be instantiated and called as such:
# obj = TopVotedCandidate(persons, times)
# param_1 = obj.q(t)

후보자들은 0 ~ len(persons) 이므로 candidate 는 인덱스 자체가 후보자 자신임

max(candidate) 로 사용하면 timelimit => maxvote 변수 따로 사용

함수 q 도 for 문으로 했다가 timelimit => Binary Search 로

---

1094. Car Pooling

You are driving a vehicle that has capacity empty seats initially available for passengers. The vehicle only drives east (ie. it cannot turn around and drive west.)

Given a list of trips, trip[i] = [num_passengers, start_location, end_location] contains information about the i-th trip: the number of passengers that must be picked up, and the locations to pick them up and drop them off. The locations are given as the number of kilometers due east from your vehicle's initial location.

Return true if and only if it is possible to pick up and drop off all passengers for all the given trips.

My Answer 1: Accepted (Runtime: 60 ms - 82.75% / Memory Usage: 14.9 MB - 51.37%)

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        dic = collections.defaultdict(int)
        
        for i in range(len(trips)):
            dic[trips[i][1]] += trips[i][0]
            dic[trips[i][2]] -= trips[i][0]
        dic = sorted(dic.items())
        
        car = 0
        for i in range(len(dic)):
            car += dic[i][1]
            if car > capacity:
                return False
        
        return True

dic 에 태우고 내려주는 위치마다 인원값을 update
태우면 +num 내려주면 -num

위치를 기준으로 정렬해주고 순서대로 인원값의 변화를 더해주기
=> capacity 를 초과하게 되면 return False