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

from sortedcontainers import SortedList

class Solution:
    def minGroups(self, intervals: List[List[int]]) -> int:
        intervals = sorted(intervals, key=lambda it: it[-1])
        groups = SortedList()
 
        for left, right in intervals:
            k = groups.bisect_left(left)
            if not k:
                groups.add(right)
            else:
                groups.remove(groups[k - 1])
                groups.add(right)

        return len(groups)

class Solution {
    public int minGroups(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> {
            return a[0] - b[0];
        });
        int res = 0;
        PriorityQueue<Integer> rights = new PriorityQueue<>();
        int left;
        int right;
        for (int[] interval : intervals) {
            left = interval[0];
            right = interval[1];
            if (!rights.isEmpty()) {
                if (rights.peek().intValue() < left) {
                    rights.poll();
                }
            }
            rights.add(right);
            res = Math.max(res, rights.size());

        }
        return res;
    }
}

class Solution {
    public int minGroups(int[][] intervals) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int[] interval:intervals){
            map.put(interval[0], map.getOrDefault(interval[0],0)+1);
            map.put(interval[1]+1, map.getOrDefault(interval[1]+1,0)-1);
        }
        List<Integer> key_list = map.keySet().stream().sorted().collect(Collectors.toList());
        int res = 0;
        int cur_line =0;
        for(Integer key:key_list){
            cur_line+=map.get(key);
            res = Math.max(res, cur_line);
        }
        return res;
    }
}

class Solution {
public:
    int minGroups(vector<vector<int>>& intervals) {
        map<int, int> mark;
        for (auto interval : intervals) {
            int start = interval[0];
            int end = interval[1] + 1;
            mark[start] += 1;
            mark[end] -= 1;
        }
        int res = 0;
        int sum = 0;
        for (auto iter = mark.begin(); iter != mark.end(); iter++) {
            sum += iter->second;
            res = max(res, sum);
        }
        return res;
    }
};

public class Solution
{
    public int MinGroups(int[][] intervals)
    {
        Array.Sort(intervals, (a, b) => a[0] - b[0]);
        int nextRoom = 1;
        PriorityQueue<(int, int), int> q = new(); // end, room, end
        List<int> availableRooms = new();

        int result = nextRoom;
        for (int i = 0; i < intervals.Length; i++)
        {
            int[] meeting = intervals[i];
            while (q.Count > 0)
            {
                (int endTime, int room) = q.Peek();
                if (meeting[0] <= endTime)
                {
                    break;
                }
                availableRooms.Add(q.Dequeue().Item2);
            }

            int useRoom;
            if (availableRooms.Count == 0)
            {
                useRoom = nextRoom;
                nextRoom++;
            }
            else
            {
                useRoom = availableRooms[^1];
                availableRooms.RemoveAt(availableRooms.Count - 1);
            }
            result = Math.Max(result, useRoom);
            q.Enqueue((meeting[1], useRoom), meeting[1]);
        }

        return result;
    }
}

class Solution {
    public int minGroups(int[][] intervals) {
        if(intervals.length == 1)   return 1;
        TreeMap<Integer,Integer> map = new TreeMap();
        int res = 0;
        int sum = 0;
        for(int[] i: intervals){
            map.put(i[0],map.getOrDefault(i[0],0)+1);
            map.put(i[1]+1,map.getOrDefault(i[1]+1,0)-1);
        }
        for(int i:map.keySet()){
            sum+=map.get(i);
            res=Math.max(sum,res);
        }
        return res;
    }
}

impl Solution {
    pub fn min_groups(intervals: Vec<Vec<i32>>) -> i32 {
        let mut freqs: Vec<(i32, i32)> = vec![];

        for interval in intervals {
            let (l, r) = (interval[0], interval[1] + 1);

            freqs.push((l, 1));
            freqs.push((r, -1));
        }

        freqs.sort_unstable();

        let (mut count, mut max_count) = (0, 1);

        for (time, freq) in freqs {
            count += freq;
            max_count = max_count.max(count);
        }

        max_count.abs()
    }
}

class Solution:
    def minGroups(self, intervals: List[List[int]]) -> int:
        minn = 0

        intervals.sort()
        endHeap = []

        for i in range(len(intervals)):
            if endHeap and intervals[i][0] > endHeap[0]:
                heappop(endHeap)
            else:
                minn += 1
            heappush(endHeap, intervals[i][1])

        return minn

use std::cmp::Reverse;
use std::collections::*;

impl Solution {
    pub fn smallest_chair(mut times: Vec<Vec<i32>>, target_friend: i32) -> i32 {
        let (n, target_friend) = (times.len(), target_friend as usize);

        let mut unoccupied_chairs: BinaryHeap<Reverse<usize>> =
            (0..n).map(|i| Reverse(i)).collect();

        let mut occupied_chairs: HashMap<usize, usize> = HashMap::new();

        let mut events: Vec<(i32, bool, usize)> =
            times.into_iter().enumerate().
                fold(vec![], |mut acc, (i, time)| {
                    let (l, r) = (time[0], time[1]);

                    acc.push((l, true, i));
                    acc.push((r, false, i));

                    acc
                });

        events.sort_unstable();

        for (time, arriving, friend) in events {
            if arriving {
                let Reverse(chair) = unoccupied_chairs.pop().unwrap();

                if friend == target_friend {
                    return chair as i32;
                }

                occupied_chairs.insert(friend, chair);
                continue;
            }

            let chair = occupied_chairs.remove(&friend).unwrap();
            unoccupied_chairs.push(Reverse(chair));
        }

        panic!() // at the disco
    }
}

class Solution {
    public int minGroups(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> a - b);
        for (int[] interval : intervals) {
            int l = interval[0];
            int r = interval[1];
            if (pq.isEmpty()) pq.offer(r);
            else {
                if (l > pq.peek()) {
                    pq.poll();
                    pq.offer(r);
                } else {
                    pq.offer(r);
                }
            }
        }
        return pq.size();
    }
}

class Solution {
public:
    int minGroups(vector<vector<int>>& intervals) {
        auto points = map<int, int>{};
        for (const auto& segment : intervals) {
            ++points[segment[0]]; --points[segment[1] + 1];
        }
        auto prefixSum = 0; auto maxPrefixSum = 0;
        for (const auto& [_, v] : points) {
            if ((prefixSum += v) > maxPrefixSum) maxPrefixSum = prefixSum;
        }
        return maxPrefixSum;
    }
};

use std::collections::HashMap;

impl Solution {
    pub fn smallest_range(nums: Vec<Vec<i32>>) -> Vec<i32> {
        let k = nums.len();

        let mut sorted: Vec<(i32, usize)> =
            nums.into_iter().enumerate().
                flat_map(|(i, list)| {
                    list.into_iter().
                        map(|num| (num, i)).
                        collect::<Vec<(i32, usize)>>()
                }).
                collect();

        sorted.sort_unstable();

        let mut l = 0;
        let mut seen = HashMap::new();
        let mut range: Option<(i32, i32)> = None;

        for (r, (r_point, r_list)) in sorted.iter().copied().enumerate() {
            seen.entry(r_list).and_modify(|freq| *freq += 1).or_insert(1);

            while seen.len() == k {
                let (l_point, l_list) = sorted[l];

                range =
                    range.map(|(left, right)| {
                        if r_point - l_point < right - left {
                            (l_point, r_point)
                        } else {
                            (left, right)
                        }
                    }).or(Some((l_point, r_point)));

                seen.entry(l_list).and_modify(|freq| *freq -= 1);

                if seen[&l_list] == 0 {
                    seen.remove(&l_list);
                }

                l += 1;
            }
        }

        range.map(|(left, right)| vec![left, right]).or(Some(vec![])).unwrap()
    }
}

class Solution:
    def smallestRange(self, nums: List[List[int]]) -> List[int]:
        pq = []
        left = 0
        right = inf
        maxSofar = -1
        n = len(nums)
        for i in range(n):
            maxSofar = max(maxSofar, nums[i][0])
            heapq.heappush(pq, (nums[i][0], i, 0))
        while pq:
            val, i, j = heapq.heappop(pq)
            if maxSofar - val < right - left:
                left = val
                right = maxSofar
                
            if j + 1 < len(nums[i]):
                maxSofar = max(maxSofar, nums[i][j + 1])
                heapq.heappush(pq, (nums[i][j + 1], i, j + 1))
            else:
                break
        return [left, right]

class Solution {
    public int[] smallestRange(List<List<Integer>> nums) {
        int max = Integer.MIN_VALUE, start = 0, end = Integer.MAX_VALUE;
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        int i = 0;
        for (List<Integer> list : nums) {
            pq.offer(new int[] {list.get(0), i, 0});
            max = Math.max(max, list.get(0));
            i++;
        }
        while (true) {
            int[] data = pq.poll();
            int min = data[0], row = data[1], col = data[2];
            if (max - min < end - start) {
                start = min;
                end = max;
            }
            if (col + 1 < nums.get(row).size()) {
                int next = nums.get(row).get(col + 1);
                pq.offer(new int[] {next, row, col + 1});
                max = Math.max(max, next);
            } else break;
        }
        return new int[] {start, end};
    }
}

public class Solution
{
    public int[] SmallestRange(IList<IList<int>> nums)
    {
        int[] arrIndices = new int[nums.Count];
        PriorityQueue<(int, int), int> q = new(); // val, arr index, val

        int currentMax = int.MinValue;
        for (int i = 0; i < nums.Count; i++)
        {
            IList<int> arr = nums[i];
            currentMax = Math.Max(currentMax, arr[0]);
            q.Enqueue((arr[0], i), arr[0]);

            arrIndices[i]++;
        }
        int[] result = new int[2];
        result[0] = q.Peek().Item1;
        result[1] = currentMax;

        while (true)
        {
            (int currentMin, int minListIndex) = q.Dequeue();
            if (currentMax - currentMin < result[1] - result[0])
            {
                result[0] = currentMin;
                result[1] = currentMax;
            }
            IList<int> minList = nums[minListIndex];
            if (arrIndices[minListIndex] == minList.Count)
            {
                break;
            }

            int nextVal = minList[arrIndices[minListIndex]];
            q.Enqueue((nextVal, minListIndex), nextVal);
            arrIndices[minListIndex]++;

            currentMax = Math.Max(currentMax, nextVal);
        }

        return result;
    }
}

class Solution {
    public int[] smallestRange(List<List<Integer>> nums) {
        int k = nums.size();
        int[] res = new int[2];
        int n = 0;
        for (List<Integer> l : nums) {
            n += l.size();
        }
        int[][] arr = new int[n][2];
        int index = 0;
        int j = 0;

        for (List<Integer> l : nums) {
            for (int i : l) {
                arr[index][0] = i;
                arr[index][1] = j;
                index++;
            }
            j++;
        }

        Arrays.sort(arr, (a, b) -> {
            return a[0] - b[0];
        });
        //System.out.println(Arrays.deepToString(arr));
        int[] counter = new int[k];
        int cnt = 0;
        int l = 0;
        int minRange = Integer.MAX_VALUE;
        for (int r = 0; r < n; r++) {
            if (counter[arr[r][1]] == 0) {
                cnt++;
            }
            counter[arr[r][1]]++;
            int left = arr[l][0];
            if (cnt == k) {
                while (l <= r && cnt == k) {
                    if (--counter[arr[l][1]] == 0)
                        cnt--;
                    left = arr[l][0];
                    l++;
                }
                int range = arr[r][0] - left;
                //System.out.println("r:" + r + "   range:"+ range);
                if (range < minRange) {
                 
                    res[0] = left;
                    res[1] = arr[r][0];
                    minRange =range;
                }
            }

        }
        return res;
    }
}