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

class Solution {

struct LeavingNode {
    int i;
    int arrival;
    int leaving;
    int order;

    LeavingNode(int _i, int _arrival, int _leaving, int _order) {
        i = _i;
        arrival = _arrival;
        leaving = _leaving;
        order = _order;
    }
    
};

class Compare
{
public:
    bool operator() (LeavingNode x, LeavingNode y){
        return x.leaving > y.leaving;
    }
};

public:
    int smallestChair(vector<vector<int>>& times, int targetFriend) {
        priority_queue<LeavingNode, std::vector<LeavingNode>, Compare> pq_leave;
        priority_queue<int, vector<int>, greater<int>> pq_order;

        int n = times.size();
        int ids[n];
        for (int i = 0; i < n; ++i) ids[i] = i;

        sort(ids, ids + n, [&times](int i, int j) { return times[i][0] < times[j][0]; });

        // for (int i : ids) cout << i << "\n";
        for (int i = 0; i < n; ++i){
            pq_order.push(i);
        }

        for (int i : ids) {
            // LeavingNode cur(i, times[i][0], times[i][1], )
            int cur_arrival = times[i][0];
            while (!pq_leave.empty()){
                auto top = pq_leave.top();
                // cout << top.i << " [" << top.arrival << "," << top.leaving << "] " << top.order << " x\n";
                if (top.leaving > cur_arrival) break;
                pq_order.push(top.order);
                pq_leave.pop();
            }
            int order = pq_order.top();
            pq_order.pop();
            if (i == targetFriend) return order;
            LeavingNode cur(i, cur_arrival, times[i][1], order);
            pq_leave.push(cur);
            // cout << i << " [" << cur_arrival << "," << times[i][1] << "] " << order << "\n";
        }

        return -1;
    }
};

class Solution:
    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:       
        startHeap = []
        endHeap = []
        seatHeap = []
        for i in range(len(times)):
            heappush(startHeap, (times[i][0], i))
            heappush(seatHeap, i)

        for i in range(len(startHeap)):
            arrivalAt, arrivalFriend = heappop(startHeap)

            while endHeap and arrivalAt >= endHeap[0][0]:
                endAt, seat = heappop(endHeap)
                heappush(seatHeap, seat)

            newSeat = heappop(seatHeap)
            heappush(endHeap, (times[arrivalFriend][1], newSeat))
            if arrivalFriend == targetFriend:
                return newSeat

        return 0

class Solution {
    public int smallestChair(int[][] times, int targetFriend) {
        int n = times.length;
        PriorityQueue<Integer> available_chairs = new PriorityQueue();
        PriorityQueue<int[]> leaving = new PriorityQueue<>((a,b)->{
            return a[0]-b[0];
        });
        int index =0;
        int max =0;
        int chair =0;
        Map<Integer,Integer> mapper = new HashMap();
      
        for(int[] time:times){
            mapper.put(time[0], index++);
        }
        Arrays.sort(times, (a,b)-> a[0]-b[0]);
        index =0 ;
        for(int[] time:times){
          
            int arrival_time = time[0];
            int leaving_time = time[1];
            if(!leaving.isEmpty()){
                int[] min_leaving = leaving.peek();
                while(min_leaving[0]<=arrival_time){
                    available_chairs.add(min_leaving[1]);
                    leaving.poll();
                    if(leaving.isEmpty()) break;
                    min_leaving = leaving.peek();
                }
            }
        
            if(!available_chairs.isEmpty()){
               chair = available_chairs.poll();
            }
            else {
                chair = max++;
            }
            int fr_number = mapper.get(arrival_time);
            if(fr_number == targetFriend) return chair;
          
            leaving.add(new int[]{leaving_time,chair});
          
        }
        return -1;
    }
}

class Solution {
    public int smallestChair(int[][] times, int targetFriend) {
        int n = times.length;
        Integer[] idxArr = new Integer[n];

        for (int i = 0; i < n; i++) {
            idxArr[i] = i;
        }

        Arrays.sort(idxArr, (a, b) -> {
            return times[a][0] - times[b][0];
        });

        int[] trackingArr = new int[n];

        for (int num : idxArr) {
            int arrive = times[num][0], leave = times[num][1];

            for (int i = 0; i < n; i++) {
                if (trackingArr[i] <= arrive) {
                    trackingArr[i] = leave;
                    if (num == targetFriend) {
                        return i;
                    }
                    break;
                }
            }
        }

        return 0;
    }
}

public class Solution
{
    public int SmallestChair(int[][] times, int targetFriend)
    {
        int[] target = times[targetFriend];
        Array.Sort(times, (a, b) => a[0] - b[0]);
        PriorityQueue<(int, int), int> q = new(); // timeOut, seat, timeOut
        PriorityQueue<int, int> usableChairs = new();

        int maxSeat = 0;
        for (int i = 0; i < times.Length; i++)
        {
            int[] time = times[i];
            while (q.Count > 0)
            {
                (int, int) peek = q.Peek();
                if (time[0] < peek.Item1)
                {
                    break;
                }
                int chair = q.Dequeue().Item2;
                usableChairs.Enqueue(chair, chair);
            }

            int seat;
            if (usableChairs.Count == 0)
            {
                seat = maxSeat;
                maxSeat++;
            }
            else
            {
                seat = usableChairs.Dequeue();
            }
            q.Enqueue((time[1], seat), time[1]);
            if (time[0] == target[0] && time[1] == target[1])
            {
                return seat;
            }
        }

        return -1;
    }
}

class Solution:
    def minGroups(self, intervals: List[List[int]]) -> int:
        lines = set()
        countStart = defaultdict(int)
        countEnd = defaultdict(int)
        for start, end in intervals:
            countStart[start] += 1
            countEnd[end] -= 1
            lines.add(start)
            lines.add(end)

        lines = sorted(lines)
        groups = 0
        ans = 0
        for l in lines:
            groups += countStart[l]
            ans = max(ans, groups)
            groups += countEnd[l]

        return ans

class Solution:
    def minGroups(self, intervals: List[List[int]]) -> int:
        heap = []
        for left, right in intervals:
            heapq.heappush(heap, (left, right))
        group = []

        while heap:
            left, right = heapq.heappop(heap)
            if group and group[0] < left:
                heapq.heappop(group)
            heapq.heappush(group, right)
        return len(group)

class Solution:
    def minGroups(self, A: List[List[int]]) -> int:
        A = sorted(A)
        q = []
        for s,e in A:
            if q and q[0] < s:
                heapq.heappop(q)
            heapq.heappush(q, e)
        return len(q)

var minGroups = function (intervals) {
    intervals.sort((u, v) => u[0] - v[0]);
    const pq = new MinPriorityQueue();
    let ans = 0, free = 0;
    for (const [u, v] of intervals) {
        while (!pq.isEmpty() && pq.front().element < u) {
            pq.dequeue();
            free++;
        }
        if (free > 0) {
            free--;
        } else {
            ans++;
        }
        pq.enqueue(v);
    }
    return ans;
};