Divide Intervals Into Minimum Number of Groups LeetCode Solution

Problem – Divide Intervals Into Minimum Number of Groups LeetCode Solution

You are given a 2D integer array intervals where intervals[i] = [lefti, righti] represents the inclusive interval [lefti, righti].

You have to divide the intervals into one or more groups such that each interval is in exactly one group, and no two intervals that are in the same group intersect each other.

Return the minimum number of groups you need to make.

Two intervals intersect if there is at least one common number between them. For example, the intervals [1, 5] and [5, 8] intersect.

Example 1:

Input: intervals = [[5,10],[6,8],[1,5],[2,3],[1,10]]
Output: 3
Explanation: We can divide the intervals into the following groups:
- Group 1: [1, 5], [6, 8].
- Group 2: [2, 3], [5, 10].
- Group 3: [1, 10].
It can be proven that it is not possible to divide the intervals into fewer than 3 groups.

Example 2:

Input: intervals = [[1,3],[5,6],[8,10],[11,13]]
Output: 1
Explanation: None of the intervals overlap, so we can put all of them in one group.

Constraints:

• 1 <= intervals.length <= 105
• intervals[i].length == 2
• 1 <= lefti <= righti <= 106

Divide Intervals Into Minimum Number of Groups LeetCode Solution in Java

    public int minGroups(int[][] intervals) {
        int res = 0, cur = 0, n = intervals.length, A[][] = new int[n * 2][2];
        for (int i = 0; i < n; ++i) {
            A[i * 2] = new int[]{intervals[i][0], 1};
            A[i * 2 + 1] = new int[]{intervals[i][1] + 1, -1};
        }
        Arrays.sort(A, Comparator.comparingInt(o -> o[0] * 3 + o[1]));
        for (int[] a: A)
            res = Math.max(res, cur += a[1]);
        return res;
    }

Divide Intervals Into Minimum Number of Groups LeetCode Solution in C++

    int minGroups(vector<vector<int>>& intervals) {
        vector<vector<int>> A;
        for (auto& v : intervals) {
            A.push_back({v[0], 1});
            A.push_back({v[1] + 1, -1});
        }
        int res = 0, cur = 0;
        sort(A.begin(), A.end());
        for (auto& v : A)
            res = max(res, cur += v[1]);
        return res;
    }

Divide Intervals Into Minimum Number of Groups LeetCode Solution in Python

    def minGroups(self, intervals):
        A = []
        for a,b in intervals:
            A.append([a, 1])
            A.append([b + 1, -1])
        res = cur = 0
        for a, diff in sorted(A):
            cur += diff
            res = max(res, cur)
        return res

Divide Intervals Into Minimum Number of Groups LeetCode Solution Review:

In our experience, we suggest you solve this Divide Intervals Into Minimum Number of Groups LeetCode Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Divide Intervals Into Minimum Number of Groups LeetCode Solution

Find on Leetcode

Conclusion:

I hope this Divide Intervals Into Minimum Number of Groups LeetCode Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

LeetCode Solutions

Hacker Rank Solutions

CodeChef Solutions