LC-2406 Medium LeetCode

2406. Divide Intervals Into Minimum Number of Groups

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

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 64% Topics: Array, Two Pointers, Greedy, Sorting, Heap (Priority Queue), Prefix Sum

Reading material

Arrays & Hashing 12 min Two Pointers 9 min Greedy 11 min

Reference solution (spoiler · python)

# Time:  O(nlogn)
# Space: O(n)

import collections


# sort, line sweep
class Solution(object):
    def minGroups(self, intervals):
        """
        :type intervals: List[List[int]]
        :rtype: int
        """
        events = collections.Counter()
        for l, r in intervals:
            events[l] += 1
            events[r+1] -= 1
        result = curr = 0
        for t in sorted(events.iterkeys()):
            curr += events[t]
            result = max(result, curr)
        return result

Solution from kamyu104/LeetCode-Solutions · MIT