Assign Intervals to Groups

You are given an array intervals, where intervals[i] = [start, end] is a closed interval covering every point from start to end inclusive.

Two intervals clash when they share at least one point. Because the intervals are closed, touching counts: [1, 2] and [2, 4] clash, while [1, 2] and [3, 4] do not.

Place every interval into a numbered group so that no group holds two clashing intervals, using as few groups as possible. Groups are numbered $1, 2, 3, \ldots$

Many placements use the fewest groups, so exactly one of them is singled out. Build the placement this way:

• Consider the intervals in nondecreasing order of start. If two intervals share a start, consider the one that appears earlier in intervals first.
• Give each interval the smallest-numbered group that holds nothing it clashes with. Open a new group only when every group already in use would clash.

Return an array answer of the same length as intervals, where answer[i] is the group number given to intervals[i], in the same order as the input. The number of groups used is the largest value in answer.

Examples

Example 1

Input: intervals = [[1,2],[2,4],[4,4]]
Output: [1,2,1]
Explanation: [1,2] opens group 1. [2,4] clashes with it at the point 2, so it opens group 2.
[4,4] does not clash with [1,2] (which ends at 2), so group 1 is free again and is the
smallest free number. Two groups are enough, and no placement uses fewer.

Example 2

Input: intervals = [[3,5],[1,4],[6,8],[3,9]]
Output: [2,1,1,3]
Explanation: Start order is [1,4], then [3,5] and [3,9] (both start at 3, so the earlier
index goes first), then [6,8]. [1,4] takes group 1. [3,5] clashes with it, so it takes
group 2. [3,9] clashes with both, so it takes group 3. By the time [6,8] is placed, groups
1 and 2 are free ([1,4] and [3,5] both end before 6) and the smaller number wins.