There is a long and thin painting that can be represented by a number line. The painting was painted with multiple overlapping segments where each segment was painted with a unique color. You are given a 2D integer array segments, where segments[i] = [starti, endi, colori] represents the half-closed segment [starti, endi) with colori as the color.
The colors in the overlapping segments of the painting were mixed when it was painted. When two or more colors mix, they form a new color that can be represented as a set of mixed colors.
2, 4, and 6 are mixed, then the resulting mixed color is {2,4,6}.For the sake of simplicity, you should only output the sum of the elements in the set rather than the full set.
You want to describe the painting with the minimum number of non-overlapping half-closed segments of these mixed colors. These segments can be represented by the 2D array painting where painting[j] = [leftj, rightj, mixj] describes a half-closed segment [leftj, rightj) with the mixed color sum of mixj.
segments = [[1,4,5],[1,7,7]] can be described by painting = [[1,4,12],[4,7,7]] because:
[1,4) is colored {5,7} (with a sum of 12) from both the first and second segments.[4,7) is colored {7} from only the second segment.Return the 2D array painting describing the finished painting (excluding any parts that are not painted). You may return the segments in any order.
A half-closed segment [a, b) is the section of the number line between points a and b including point a and not including point b.
Example 1:
Input: segments = [[1,4,5],[4,7,7],[1,7,9]]
Output: [[1,4,14],[4,7,16]]
Explanation: The painting can be described as follows:
- [1,4) is colored {5,9} (with a sum of 14) from the first and third segments.
- [4,7) is colored {7,9} (with a sum of 16) from the second and third segments.
Example 2:
Input: segments = [[1,7,9],[6,8,15],[8,10,7]]
Output: [[1,6,9],[6,7,24],[7,8,15],[8,10,7]]
Explanation: The painting can be described as follows:
- [1,6) is colored 9 from the first segment.
- [6,7) is colored {9,15} (with a sum of 24) from the first and second segments.
- [7,8) is colored 15 from the second segment.
- [8,10) is colored 7 from the third segment.
Example 3:
Input: segments = [[1,4,5],[1,4,7],[4,7,1],[4,7,11]]
Output: [[1,4,12],[4,7,12]]
Explanation: The painting can be described as follows:
- [1,4) is colored {5,7} (with a sum of 12) from the first and second segments.
- [4,7) is colored {1,11} (with a sum of 12) from the third and fourth segments.
Note that returning a single segment [1,7) is incorrect because the mixed color sets are different.
Constraints:
1 <= segments.length <= 2 * 104segments[i].length == 31 <= starti < endi <= 1051 <= colori <= 109colori is distinct.This approach involves representing each segment's start and end as events on the number line. We use a sweep line technique to iterate through sorted events, maintaining a running count of active segments and calculating the mixed color sums in between events.
In this C implementation, we handle segments as events (starting and ending). Using an array of these events, we sort them by position. As we iterate through the sorted events, we maintain a running sum of active color segments using a simple array to represent active segments, updating this as we encounter start and end events. Segments are added to the painting result whenever there is an interval between events and the sum of active segments is positive.
C++
Java
Python
C#
JavaScript
Time complexity: O(n log n) due to sorting of events (where n is the number of segment endpoints).
Space complexity: O(n) for storing events and managing active segments.
An interval tree can help manage overlapping segments and mixed colors efficiently. Use an interval tree structure to add segments and query overlapping intervals as you iterate through the segments, dynamically updating and storing mixed color sums.
Implementing a sophisticated data structure like an interval tree efficiently in C requires detailed handling of pointers and possibly creating multiple struct extensions. With this approach, the interval tree dynamically manages color ranges, updating mixes as segments are inserted or queried.
C++
Java
Python
C#
JavaScript
The complexity largely depends on the interval tree implementation but can be efficient with many operations falling under O(log n) for both insertions and queries, leading to a global complexity of O(n log n).
| Approach | Complexity |
|---|---|
| Sweep Line Technique with Events | Time complexity: O(n log n) due to sorting of events (where n is the number of segment endpoints). |
| Interval Tree Approach | The complexity largely depends on the interval tree implementation but can be efficient with many operations falling under O(log n) for both insertions and queries, leading to a global complexity of O(n log n). |
Can Place Flowers - Leetcode 605 - Python • NeetCode • 55,552 views views
Watch 9 more video solutions →Practice Describe the Painting with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor