LeetCode Entry

2406. Divide Intervals Into Minimum Number of Groups

12.10.2024 medium 2024 kotlin rust

Count non-intersecting groups of intervals

2406. Divide Intervals Into Minimum Number of Groups medium blog post substack youtube 1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/766

Problem TLDR

Count non-intersecting groups of intervals #medium #heap #sorting

Intuition

Let’s observe the intervals’ properties:


    // 5,10 6,8 1,5 2,3 1,10   n=5
    //
    // 1 2 3 4 5 6 7 8 9 10
    //         . . . . . .  5->take min g3(10)
    //           . . .      6->take min g1(5)
    // . . . . .             g1(5)
    //   . .                 g3(3)
    // . . . . . . . . . .   g2(10)

If we use sweep line algorithm, then we should peek the first non-intersecting group or add another group. To track the groups, let’s maintain a heap with ends of each group.

Another way to solve this is to notice some observation: groups count is the maximum intersecting intervals count (but it should be proved somehow, it is just works magically)

Approach

  • to sweep line to work, we should sort for both ends and starts to be in increasing order
  • for the second way, we can use counting sorting

Complexity

  • Time complexity: \(O(n)\) or O(nlog(n))

  • Space complexity: \(O(m)\) or O(n)

Code


    fun minGroups(intervals: Array<IntArray>): Int {
        intervals.sortWith(compareBy({ it[0] }, { it[1] }))
        val ends = PriorityQueue<Int>()
        for ((a, b) in intervals) {
            if (ends.size > 0 && a > ends.peek()) ends.poll()
            ends += b
        }
        return ends.size
    }



    pub fn min_groups(intervals: Vec<Vec<i32>>) -> i32 {
        let (mut ends, mut curr) = (vec![0; 1_000_002], 0);
        for iv in intervals {
            ends[iv[0] as usize] += 1; ends[1 + iv[1] as usize] -= 1; }
        ends.iter().map(|e| { curr += e; curr }).max().unwrap()
    }



    int minGroups(vector<vector<int>>& intervals) {
        int ends[1000002] = {}, curr = 0, res = 0;
        for (auto iv: intervals) ends[iv[0]]++, ends[iv[1] + 1]--;
        for (int e: ends) res = max(res, curr += e);
        return res;
    }