(similar to 253 )2406. Divide Intervals Into Minimum Number of Groups

actually it's same meaning to 253, but inclusive end time

linesweep

end time is inclusive, so need to add 1

class Solution {
    public int minGroups(int[][] intervals) {
        TreeMap<Integer, Integer> map = new TreeMap<>();
        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);
        }

        int roomCount = 0;
        int result = 0;
        for (int time : map.keySet()) {
            roomCount += map.get(time);
            result = Math.max(result, roomCount);
        }
        return result;
    }
}

Heap (1942 style)

result + 1, because it's the group no, we need count, so +1

class Solution {
    private record Group(int endTime, int group){};
    public int minGroups(int[][] intervals) {
        int n = intervals.length;
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        Queue<Integer> av = new PriorityQueue<>();
        Queue<Group> oc = new PriorityQueue<>((a, b) -> a.endTime - b.endTime);
        for (int i = 0; i < n; i++) {
            av.offer(i);
        }
        int result = 0;
        for (int[] in : intervals) {
            int start = in[0];
            int end = in[1];
            while (!oc.isEmpty() && oc.peek().endTime < start) {
                av.offer(oc.poll().group);
            }
            int group = av.poll();
            oc.offer(new Group(end, group));
            result = Math.max(result, group);
        }
        return result + 1;
    }
}

Heap

one heap

class Solution {
    public int minGroups(int[][] intervals) {
        int n = intervals.length;
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        Queue<Integer> endTimeHeap = new PriorityQueue<>();

        int result = 0;
        for (int[] in : intervals) {
            int start = in[0];
            int end = in[1];
            while (!endTimeHeap.isEmpty() && endTimeHeap.peek() < start) {
                endTimeHeap.poll();
            }
            endTimeHeap.offer(end);
            result = Math.max(result, endTimeHeap.size());
        }
        return result;
    }
}