Divide Intervals Into Minimum Number of Groups

Divide Intervals Into Minimum Number of Groups - Problem

Array Two Pointers Greedy Sorting Heap (Priority Queue) Prefix Sum Medium

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

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.

Input & Output

Example 1 — Basic Overlapping

$ Input: intervals = [[5,10],[6,8],[1,5],[2,3],[1,10]]

› Output: 3

💡 Note: We can divide into 3 groups: Group 1: [[1,5],[6,8]], Group 2: [[5,10]] (note [1,5] and [5,10] intersect at 5), Group 3: [[2,3],[1,10]] won't work since they overlap. Better grouping: Group 1: [[1,5]], Group 2: [[6,8]], Group 3: [[5,10],[2,3]] won't work. Optimal: Group 1: [[1,5],[6,8]], Group 2: [[2,3]], Group 3: [[5,10],[1,10]] - but [5,10] and [1,10] overlap. Actually: intervals [1,5], [2,3], [1,10] all overlap with each other, so need 3 groups minimum.

Example 2 — No Overlaps

$ Input: intervals = [[1,3],[5,6],[8,10],[11,13]]

› Output: 1

💡 Note: No intervals overlap since each ends before the next begins, so all can go in one group: [[1,3],[5,6],[8,10],[11,13]]

Example 3 — Maximum Overlap

$ Input: intervals = [[1,10],[2,10],[3,10],[4,10]]

› Output: 4

💡 Note: All intervals overlap with each other since they all contain points 4-10, so each needs its own group

Constraints

1 ≤ intervals.length ≤ 10⁵
intervals[i].length == 2
1 ≤ left_i ≤ right_i ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input Intervals

Given intervals that may overlap with each other

Group Assignment

Assign each interval to a group where no two intervals overlap

Minimum Groups

Find the minimum number of groups needed

Key Takeaway

🎯 Key Insight: The minimum groups needed equals the maximum number of intervals overlapping at any single point in time

Asked in

G Google 45 M Microsoft 38 a Amazon 32 Apple 28

The key insight is that the minimum number of groups needed equals the maximum number of intervals that overlap at any point in time. The optimal approach uses a priority queue to efficiently track group end times, achieving O(n log n) time complexity.

Common Approaches

Approach	Time	Space	Notes
✓ Event Point Counting	O(n log n)	O(n)	Count maximum simultaneous intervals using start/end events
Brute Force Grouping	O(n²)	O(n)	Try to place each interval in existing groups, create new group if needed
Priority Queue (Min Heap)	O(n log n)	O(n)	Sort intervals by start time, use heap to track earliest ending times

Event Point Counting — Algorithm Steps

Create start/end events for each interval
Sort all events by time
Track running count and find maximum

Visualization

Tap to expand

Step-by-Step Walkthrough

Create Events

Each interval creates start (+1) and end (-1) events

Process Timeline

Sort events and track running count

Find Maximum

Maximum count equals minimum groups needed

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int time;
    int delta;
} Event;

int compareEvents(const void* a, const void* b) {
    Event* e1 = (Event*)a;
    Event* e2 = (Event*)b;
    if (e1->time == e2->time) {
        return e1->delta - e2->delta;
    }
    return e1->time - e2->time;
}

int solution(int intervals[][2], int n) {
    if (n == 0) return 0;
    
    Event events[2000]; // 2*n events max
    int eventCount = 0;
    
    for (int i = 0; i < n; i++) {
        events[eventCount++] = (Event){intervals[i][0], 1};     // interval starts
        events[eventCount++] = (Event){intervals[i][1] + 1, -1}; // interval ends (end+1 because intervals are inclusive)
    }
    
    // Sort events by time, process end events before start events for same time
    qsort(events, eventCount, sizeof(Event), compareEvents);
    
    int maxGroups = 0;
    int currentGroups = 0;
    
    for (int i = 0; i < eventCount; i++) {
        currentGroups += events[i].delta;
        if (currentGroups > maxGroups) {
            maxGroups = currentGroups;
        }
    }
    
    return maxGroups;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int intervals[1000][2];
    int n = 0;
    
    if (strcmp(line, "[]\n") == 0) {
        printf("0\n");
        return 0;
    }
    
    char *ptr = line + 1; // Skip first [
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            intervals[n][0] = atoi(ptr);
            while (*ptr && *ptr != ',') ptr++;
            ptr++; // Skip comma
            intervals[n][1] = atoi(ptr);
            while (*ptr && *ptr != ']') ptr++;
            ptr++; // Skip ]
            n++;
        }
        ptr++;
    }
    
    int result = solution(intervals, n);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Creating 2n events takes O(n), sorting takes O(n log n)

⚡ Linearithmic

Space Complexity

O(n)

Store 2n events (start and end for each interval)

⚡ Linearithmic Space

28.4K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Event Point Counting — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler