thảo luận Leetcode mỗi ngày

class Solution:
    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:
        heap = []
        for i, time in enumerate(times):
            heapq.heappush(heap, (time[0], time[1], i))
        
        n = len(times)
        available = [0] * n

        result = n
        while heap:
            arrival, leaving, index = heapq.heappop(heap)
            i = 0
            while i < n:
                if available[i] <= arrival:
                    available[i] = leaving
                    break
                i += 1
            if index == targetFriend:
                result = i
                break
        return result

class Solution:
    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:
        currentChair = 0
        n = len(times)

        occupied = []
        unoccupied = []
        # start, end, index
        indicies = [[times[i][0], times[i][1], i] for i in range(n)]
        indicies = sorted(indicies)
        for i in range(n):
            arrival, leaving, index = indicies[i]
            while occupied and occupied[0][0] <= arrival:
                _, seat = heapq.heappop(occupied)
                heapq.heappush(unoccupied, seat)

            seat = -1
            if unoccupied:
                seat = heapq.heappop(unoccupied)
            else:
                seat = currentChair
                currentChair += 1

            if index == targetFriend:
                return seat

            heapq.heappush(occupied, (leaving, seat))

        return -1

var smallestChair = function (times, targetFriend) {
    const pq1 = new MinPriorityQueue(), pq2 = new MinPriorityQueue();
    let k = 0;
    times = times.map(([a, l], i) => [a, l, i]).sort(([u], [v]) => u - v);
    for (const [a, l, i] of times) {
        while (!pq1.isEmpty() && pq1.front().priority <= a) {
            pq2.enqueue(pq1.dequeue().element);
        }
        let j;
        if (pq2.isEmpty()) {
            j = k++;
        } else {
            j = pq2.dequeue().element;
        }
        if (i === targetFriend) {
            return j;
        }
        pq1.enqueue(j, l);
    }
    return -1;
};

function smallestChair(times: number[][], f: number): number {
    const arr = times[f];
    times.sort((a, b) => a[0] - b[0]);
    const n = times.length
    const ch = new Array(n).fill(0);
    for (const time of times) {
        for (let i = 0; i < n; i++) {
            if (ch[i] <= time[0]) {
                ch[i] = time[1];
                if (time[0] === arr[0] && time[1] === arr[1]) return i
                break;
            }
        }
    }
    return 0;
};

function smallestChair(times: number[][], f: number): number {
    const avai = new MinPriorityQueue(), occu = new MinPriorityQueue({priority: x => x.leaveTime});
    const n = times.length;
    const timeline: number[][] = [];
    for (let i = 0; i < n; i++) {
        timeline.push([times[i][0], i]);
        timeline.push([times[i][1], i * -1])
    }
    timeline.sort((a,b) => a[0] - b[0]);
    for (let i = 0; i < n; i++) avai.enqueue(i)
    for (const [time, idx] of timeline) {

        while (!occu.isEmpty() && occu.front()!.element.leaveTime <= time) {
            avai.enqueue(occu.dequeue()!.element.chair)
        }
        if (idx >= 0) {
            const chair = avai.dequeue()!.element;
            if (idx === f) return chair;
            occu.enqueue({leaveTime: times[idx][1], chair})
        }
    }
    return -1;
};

public class Solution {
    public int smallestChair(int[][] times, int targetFriend) {
        int n = times.length;
        int targetArrival = times[targetFriend][0];
        int chair = 0;
        PriorityQueue<int[]> unoccupied = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        PriorityQueue<Integer> partyChair = new PriorityQueue<>();
        Arrays.sort(times, (a, b) -> a[0] - b[0]);
        for (int i = 0; i < n; i++) {
            int arrival = times[i][0];
            int leave = times[i][1];
            int curr;
            while (!unoccupied.isEmpty() && unoccupied.peek()[0] <= arrival) {
                partyChair.add(unoccupied.poll()[1]);
            }
            if (partyChair.isEmpty()) curr = chair++;
            else curr = partyChair.poll();
            unoccupied.offer(new int[] {leave, curr});
            if (arrival == targetArrival) return curr;
        }
        return 0;
    }
}

class Solution {
    func smallestChair(_ times: [[Int]], _ targetFriend: Int) -> Int {
        let tar = times[targetFriend]
        let newTimes = times.flatMap {
            $0[0] < tar[0] ? $0 : nil
        }.sorted {
            $0[0] <= $1[0]
        }
        
        var chairs:[[[Int]]] = []
        func addFriend(_ time: [Int]) -> Int {
            var isAdded = false
            for i in 0..<chairs.count {
                if chairs[i].last![1] <= time[0] {
                    chairs[i].append(time)
                    isAdded = true
                    return i
                }
            }
            chairs.append([time])
            return chairs.count-1
        }
        
        for time in newTimes {
            addFriend(time)
        }

        return addFriend(tar)
    }
}

struct Info
{
    int time{};
    int pos{};
};

class Solution {
public:
    int smallestChair(vector<vector<int>>& times, int targetFriend) {
        std::ios_base::sync_with_stdio(0);
        std::cin.tie(0);
        int sz = times.size();
        std::vector<Info> arr;
        std::vector<Info> leave;

        for (int i = 0; i < sz; ++i)
        {
            arr.emplace_back(times[i][0], i);
            leave.emplace_back(times[i][1], i);
        }

        std::sort(arr.begin(), arr.end(), [&](Info& a, Info& b){return a.time < b.time;});
        std::sort(leave.begin(), leave.end(), [&](Info& a, Info& b){return a.time < b.time;});
        std::vector<int> tmp_vec(sz);
        std::iota(tmp_vec.begin(), tmp_vec.end(), 0);
        std::priority_queue<int, std::vector<int>, std::greater<int>> seat_q(tmp_vec.begin(), tmp_vec.end());

        int cur_leave{};
        int cur_seat{};
        std::vector<int> p_seat(sz, -1);
        int cur_arr{};
        while (cur_arr < sz)
        {    
            if (arr[cur_arr].time > leave[cur_leave].time)
            {
                seat_q.push(p_seat[leave[cur_leave].pos]);
                cur_leave++;
            }
            else
            {
                while (arr[cur_arr].time == leave[cur_leave].time)
                {
                    seat_q.push(p_seat[leave[cur_leave].pos]);
                    cur_leave++;
                }
                p_seat[arr[cur_arr].pos] = seat_q.top();
                seat_q.pop();
                if (arr[cur_arr].pos == targetFriend)
                {
                    break;
                }
                cur_arr++;
            }
        }
        return p_seat[targetFriend];
    }
};

class Solution {
public:
    int maxWidthRamp(vector<int>& nums) {
        auto decreasingSeq = vector<int>{0};
        for (size_t i = 1; i < nums.size(); ++i) {
            if (nums[decreasingSeq.back()] > nums[i]) decreasingSeq.push_back(i);
        }

        auto m = 0;
        for (size_t j = nums.size(); j > 0;) {
            auto dj = 0; j -= 1;
            while (!decreasingSeq.empty() && nums[j] >= nums[decreasingSeq.back()]) {
                dj = j - decreasingSeq.back();
                decreasingSeq.pop_back();
            }
            if (m < dj) m = dj;
        }
        return m;
    }
};