<p>You are given a <strong>0-indexed</strong> integer array <code>buses</code> of length <code>n</code>, where <code>buses[i]</code> represents the departure time of the <code>i<sup>th</sup></code> bus. You are also given a <strong>0-indexed</strong> integer array <code>passengers</code> of length <code>m</code>, where <code>passengers[j]</code> represents the arrival time of the <code>j<sup>th</sup></code> passenger. All bus departure times are unique. All passenger arrival times are unique.</p>

<p>You are given an integer <code>capacity</code>, which represents the <strong>maximum</strong> number of passengers that can get on each bus.</p>

<p>When a passenger arrives, they will wait in line for the next available bus. You can get on a bus that departs at <code>x</code> minutes if you arrive at <code>y</code> minutes where <code>y &lt;= x</code>, and the bus is not full. Passengers with the <strong>earliest</strong> arrival times get on the bus first.</p>

<p>More formally when a bus arrives, either:</p>

<ul>
	<li>If <code>capacity</code> or fewer passengers are waiting for a bus, they will <strong>all</strong> get on the bus, or</li>
	<li>The <code>capacity</code> passengers with the <strong>earliest</strong> arrival times will get on the bus.</li>
</ul>

<p>Return <em>the latest time you may arrive at the bus station to catch a bus</em>. You <strong>cannot</strong> arrive at the same time as another passenger.</p>

<p><strong>Note: </strong>The arrays <code>buses</code> and <code>passengers</code> are not necessarily sorted.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> buses = [10,20], passengers = [2,17,18,19], capacity = 2
<strong>Output:</strong> 16
<strong>Explanation:</strong> Suppose you arrive at time 16.
At time 10, the first bus departs with the 0<sup>th</sup> passenger. 
At time 20, the second bus departs with you and the 1<sup>st</sup> passenger.
Note that you may not arrive at the same time as another passenger, which is why you must arrive before the 1<sup>st</sup> passenger to catch the bus.</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> buses = [20,30,10], passengers = [19,13,26,4,25,11,21], capacity = 2
<strong>Output:</strong> 20
<strong>Explanation:</strong> Suppose you arrive at time 20.
At time 10, the first bus departs with the 3<sup>rd</sup> passenger. 
At time 20, the second bus departs with the 5<sup>th</sup> and 1<sup>st</sup> passengers.
At time 30, the third bus departs with the 0<sup>th</sup> passenger and you.
Notice if you had arrived any later, then the 6<sup>th</sup> passenger would have taken your seat on the third bus.</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == buses.length</code></li>
	<li><code>m == passengers.length</code></li>
	<li><code>1 &lt;= n, m, capacity &lt;= 10<sup>5</sup></code></li>
	<li><code>2 &lt;= buses[i], passengers[i] &lt;= 10<sup>9</sup></code></li>
	<li>Each element in <code>buses</code> is <strong>unique</strong>.</li>
	<li>Each element in <code>passengers</code> is <strong>unique</strong>.</li>
</ul>

class Solution:
    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:
        pass



























class Solution:
    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:
        buses.sort()
        passengers.sort()
        queue = deque()
        idx_person = 0
        idx_last_person = 0
        person_order = []

        for idx_bus in range(len(buses)):
            
            while idx_person < len(passengers) and passengers[idx_person] <= buses[idx_bus]:
                queue.append(idx_person)
                idx_person += 1
            
            count = 0
            while queue and count < capacity:
                idx = queue.popleft()
                if idx_bus == len(buses)-1:
                    person_order.append(idx)
                count += 1

        print(person_order)
        if len(person_order) < capacity:
            return buses[-1]
        
        for idx in range(len(person_order)-1, 0, -1):
            if passengers[idx] -1 == passengers[idx-1]:
                continue
            else:
                return passengers[idx] -1
        return passengers[0]-1












class Solution:
    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:
        # Sort buses and passengers
        buses.sort()
        passengers.sort()
        
        # Queue to manage passengers in line for buses
        queue = deque()
        idx_person = 0
        latest_time = 0
        
        for idx_bus in range(len(buses)):
            # Add passengers who can catch the current bus
            while idx_person < len(passengers) and passengers[idx_person] <= buses[idx_bus]:
                queue.append(passengers[idx_person])
                idx_person += 1
            
            # Allow passengers to get on the bus until it reaches capacity
            count = 0
            while queue and count < capacity:
                latest_time = queue.popleft()
                count += 1
            
            # If this is the last bus, we need to find the latest time you can arrive
            if idx_bus == len(buses) - 1:
                # Try finding a time just before a passenger who got on the bus
                if count < capacity:
                    latest_time = buses[idx_bus]
                
                while latest_time in set(passengers):
                    latest_time -= 1
        
        return latest_time




















class Solution:
    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:
        '''
        iterate over buses
            use queue, and store passengers that can take the buses
            from queue, pop capacity people that can take the current bus. 
            store people that took the bus
        find the disconnected time
        '''
        queue = deque()
        buses.sort()
        passengers.sort()
        idx_people = 0
        people_gone = []
        for idx_bus in range(len(buses)):
            while idx_people < len(passengers) and passengers[idx_people] <= buses[idx_bus]:
                queue.append(idx_people)
                idx_people += 1
            
            rem = capacity
            while queue and rem >= 0:
                people_gone.append(queue.popleft())
                rem -= 1

        print(people_gone)
        print(passengers)
        for idx_people in range(len(people_gone)-1, 0, -1):
            if passengers[people_gone[idx_people]] - passengers[people_gone[idx_people-1]] != 1:
                return passengers[people_gone[idx_people]]-1
        return passengers[0]-1
        








class Solution:
    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:
        buses.sort()
        passengers.sort()
        idx_people = 0
        last_time = 0
        
        for bus in buses:
            count = 0
            
            # Load as many passengers as the bus can take
            while count < capacity and idx_people < len(passengers) and passengers[idx_people] <= bus:
                last_time = passengers[idx_people]
                idx_people += 1
                count += 1
        
        # The latest possible time to arrive could be just before the last passenger or just before the last bus departure time
        latest_possible_time = last_time - 1
        while latest_possible_time in passengers:
            latest_possible_time -= 1

        # If the bus is not full, it could be the bus departure time
        if count < capacity and bus not in passengers:
            latest_possible_time = max(latest_possible_time, bus)
            
        return latest_possible_time





class Solution:
    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:
        # Sort buses and passengers
        buses.sort()
        passengers.sort()
        
        # Queue to manage passengers in line for buses
        queue = deque()
        idx_person = 0
        latest_time = 0
        
        for idx_bus in range(len(buses)):
            # Add passengers who can catch the current bus
            while idx_person < len(passengers) and passengers[idx_person] <= buses[idx_bus]:
                queue.append(passengers[idx_person])
                idx_person += 1
            
            # Allow passengers to get on the bus until it reaches capacity
            count = 0
            while queue and count < capacity:
                latest_time = queue.popleft()
                count += 1

        latest_time -= 1
        while latest_time in set(passengers):
            latest_time -= 1
        return latest_time



















class Solution:
    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:
        buses.sort()
        passengers.sort()
        idx_people = 0
        last_time = 0
        
        for bus in buses:
            count = 0
            
            # Load as many passengers as the bus can take
            while count < capacity and idx_people < len(passengers) and passengers[idx_people] <= bus:
                last_time = passengers[idx_people]
                idx_people += 1
                count += 1
        
        # The latest possible time to arrive could be just before the last passenger or just before the last bus departure time
        latest_possible_time = last_time - 1
        while latest_possible_time in passengers:
            latest_possible_time -= 1

        # If the bus is not full, it could be the bus departure time
        if count < capacity and bus not in passengers:
            latest_possible_time = max(latest_possible_time, bus)
            
        return latest_possible_time



class Solution:
    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:
        buses.sort()
        passengers.sort()
        queue = deque()

        idx_passenger = 0
        last_passenger = 0
        for idx_bus in range(len(buses)):
            while idx_passenger < len(passengers) and buses[idx_bus] >= passengers[idx_passenger]:
                queue.append(idx_passenger)
                idx_passenger += 1
            
            rem = capacity
            while queue and rem > 0:
                last_passenger = queue.popleft()
                rem -= 1

        latest_time = passengers[last_passenger]
        latest_time -= 1
        passengers_set = set(passengers)
        while latest_time in passengers_set:
            latest_time -= 1

        if rem > 0 and buses[idx_bus] not in passengers_set:
            latest_time = max(latest_time, buses[idx_bus])
        return latest_time



class Solution:
    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:
        buses.sort()
        passengers.sort()
        queue = deque()

        idx_passenger = 0
        last_possible_time = 0
        for idx_bus in range(len(buses)):
            while idx_passenger < len(passengers) and buses[idx_bus] >= passengers[idx_passenger]:
                queue.append(passengers[idx_passenger])
                idx_passenger += 1
            
            rem = capacity
            while queue and rem > 0:
                last_possible_time = queue.popleft()
                rem -= 1

        # Case 1. 마지막 승객이 탑승한 보다 이전이면서, 아무도 타지 않은 비어있는 시각을 찾는다. 
        last_possible_time -= 1
        passengers_set = set(passengers)
        while last_possible_time in passengers_set:
            last_possible_time -= 1

        # Case 2. 만약, 마지막 버스가 꽉 차지 않았다면, 그리고 버스가 떠나는 시각에 도달한 승객이 없다면, 
        #   버스가 출발하는 시각에 도달하면 됨. 
        if rem > 0 and buses[idx_bus] not in passengers_set:
            last_possible_time = max(last_possible_time, buses[idx_bus])
        return last_possible_time

class Solution:
    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:
        buses.sort()
        passengers.sort()
        queue = deque()
        last_time = 0
        idx_p = 0
        for idx_bus in range(len(buses)):
            while idx_p < len(passengers) and passengers[idx_p] <= buses[idx_bus]:
                queue.append(passengers[idx_p])
                idx_p += 1
            
            rem = capacity
            while rem > 0 and queue:
                last_time = queue.popleft()
                rem -= 1

        # case 1. find discontinuity
        last_time -= 1
        p_set = set(passengers)
        while last_time in p_set:
            last_time -= 1
        
        # case 2. if the last bus is not full
        if rem > 0 and buses[idx_bus] not in p_set:
            last_time = max(last_time, buses[idx_bus])
        return last_time























class Solution:
    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:
        buses.sort()
        passengers.sort()
        queue = deque()
        idx_p = 0
        last_p_time = 0
        for idx_b in range(len(buses)):
            bus_time = buses[idx_b]
            
            while idx_p < len(passengers) and passengers[idx_p] <= bus_time:
                queue.append(passengers[idx_p])
                idx_p += 1
            
            cap_rem = capacity
            while queue and cap_rem > 0:
                last_p_time = queue.popleft()
                cap_rem -= 1
        
        # case 1. find the discontinuity
        p_set = set(passengers)
        last_available = last_p_time - 1
        while last_available in p_set:
            last_available -= 1
        
        # case 2. empty last bus
        if cap_rem > 0 and last_p_time != buses[-1]:
            last_available = max(last_available, buses[-1])
        return last_available

class Solution:
    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:
        buses.sort()
        passengers.sort()

        last_p = 0
        last_t = 0
        idx_p = 0
        rem = 0
        queue = deque()
        for idx_b in range(len(buses)):
            # wait queue
            while idx_p < len(passengers) and passengers[idx_p] <= buses[idx_b]:
                queue.append(idx_p)
                idx_p += 1

            rem = capacity
            while queue and rem > 0:
                last_p = queue.popleft()
                last_t = passengers[last_p]
                rem -= 1

        set_t = set(passengers)
        # case 1. find the time gap between the people took the bus
        last_t -= 1
        while last_t in set_t:
            last_t -= 1
        # case 2. check if the last bus not full, and there is no person at the last min
        if rem > 0 and last_t != buses[-1]:
            last_t = max(last_t, buses[-1])
        return last_t























class Solution:
    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:
        buses.sort()
        passengers.sort()
        queue = deque()
        idx_p = 0
        cap_rem = 0
        last_time = 0
        for idx_b in range(len(buses)):
            while idx_p < len(passengers) and passengers[idx_p] <= buses[idx_b]:
                queue.append(passengers[idx_p])
                idx_p += 1
            
            cap_rem = capacity
            while cap_rem > 0 and queue:
                last_time = queue.popleft()
                cap_rem -= 1
            
        last_tt = last_time
        last_time -= 1
        set_p = set(passengers)
        while last_time in set_p:
            last_time -= 1
        
        if cap_rem > 0 and buses[-1] != last_tt:
            last_time = max(last_time, buses[-1])
        return last_time
596