1943. Describe the Painting Medium

1/**
2 * [1943] Describe the Painting
3 *
4 * 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.
5 * 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.
6 * 
7 * 	For example, if colors 2, 4, and 6 are mixed, then the resulting mixed color is {2,4,6}.
8 * 
9 * For the sake of simplicity, you should only output the sum of the elements in the set rather than the full set.
10 * 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.
11 * 
12 * 	For example, the painting created with segments = [[1,4,5],[1,7,7]] can be described by painting = [[1,4,12],[4,7,7]] because:
13 * 	
14 * 		[1,4) is colored {5,7} (with a sum of 12) from both the first and second segments.
15 * 		[4,7) is colored {7} from only the second segment.
16 * 	
17 * 	
18 * 
19 * Return the 2D array painting describing the finished painting (excluding any parts that are not painted). You may return the segments in any order.
20 * 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.
21 *  
22 * Example 1:
23 * <img alt="" src="https://assets.leetcode.com/uploads/2021/06/18/1.png" style="width: 529px; height: 241px;" />
24 * Input: segments = [[1,4,5],[4,7,7],[1,7,9]]
25 * Output: [[1,4,14],[4,7,16]]
26 * Explanation: The painting can be described as follows:
27 * - [1,4) is colored {5,9} (with a sum of 14) from the first and third segments.
28 * - [4,7) is colored {7,9} (with a sum of 16) from the second and third segments.
29 * 
30 * Example 2:
31 * <img alt="" src="https://assets.leetcode.com/uploads/2021/06/18/2.png" style="width: 532px; height: 219px;" />
32 * Input: segments = [[1,7,9],[6,8,15],[8,10,7]]
33 * Output: [[1,6,9],[6,7,24],[7,8,15],[8,10,7]]
34 * Explanation: The painting can be described as follows:
35 * - [1,6) is colored 9 from the first segment.
36 * - [6,7) is colored {9,15} (with a sum of 24) from the first and second segments.
37 * - [7,8) is colored 15 from the second segment.
38 * - [8,10) is colored 7 from the third segment.
39 * 
40 * Example 3:
41 * <img alt="" src="https://assets.leetcode.com/uploads/2021/07/04/c1.png" style="width: 529px; height: 289px;" />
42 * Input: segments = [[1,4,5],[1,4,7],[4,7,1],[4,7,11]]
43 * Output: [[1,4,12],[4,7,12]]
44 * Explanation: The painting can be described as follows:
45 * - [1,4) is colored {5,7} (with a sum of 12) from the first and second segments.
46 * - [4,7) is colored {1,11} (with a sum of 12) from the third and fourth segments.
47 * Note that returning a single segment [1,7) is incorrect because the mixed color sets are different.
48 * 
49 *  
50 * Constraints:
51 * 
52 * 	1 <= segments.length <= 2 * 10^4
53 * 	segments[i].length == 3
54 * 	1 <= starti < endi <= 10^5
55 * 	1 <= colori <= 10^9
56 * 	Each colori is distinct.
57 * 
58 */
59pub struct Solution {}
60
61// problem: https://leetcode.com/problems/describe-the-painting/
62// discuss: https://leetcode.com/problems/describe-the-painting/discuss/?currentPage=1&orderBy=most_votes&query=
63
64// submission codes start here
65
66impl Solution {
67    pub fn split_painting(segments: Vec<Vec<i32>>) -> Vec<Vec<i64>> {
68        
69    }
70}
71
72// submission codes end
73
74#[cfg(test)]
75mod tests {
76    use super::*;
77
78    #[test]
79    fn test_1943() {
80    }
81}
82