Divide Intervals Into Minimum Number of Groups

Divide Intervals Into Minimum Number of Groups is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Greedy Patterns pattern, in the Interval Merging/Scheduling subpattern.

Problem statement

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

Topics and companies

Topics: Array, Two Pointers, Greedy, Sorting, Heap (Priority Queue), Prefix Sum.

How to practise Divide Intervals Into Minimum Number of Groups on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(nlogn) time and O(n) space.

Open Divide Intervals Into Minimum Number of Groups in the code editor, or read the Divide Intervals Into Minimum Number of Groups editorial for a worked solution with its approach and complexity analysis.

Where Divide Intervals Into Minimum Number of Groups sits in the DSA pattern sheet

• Greedy Patterns pattern guide
• Interval Merging/Scheduling subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to Divide Intervals Into Minimum Number of Groups

Other problems that use the same Interval Merging/Scheduling and Greedy Patterns techniques:

• Insert Interval — Medium, same subpattern
• Merge Intervals — Medium, same subpattern
• Assign Cookies — Easy, same pattern
• Candy — Hard, same pattern
• Distant Barcodes — Medium, same pattern
• Employee Free Time — Hard, same pattern