While solving the final exam preparation course, I was faced with the following task: $$$\newline$$$ Given $$$n$$$ boxes, each with a length of $$$a_i$$$. We can put one box into another if the size of the inner one is at least 7 units smaller than the outer one, while only one other box could not be enclosed in each box, and also each box can be enclosed in a maximum of one other. Let's call a set of boxes nested inside each other a block. The task asks you to arrange the boxes so as to minimize the number of blocks. $$$\newline$$$ Obviously, this problem can be solved as follows (and this solution will definitely be correct): we are building a graph in which there will be an edge $$$i\rightarrow j$$$, if $$$a_i - 7\ge a_j$$$, this graph obviously will not have cycles. Now a block of nested boxes will look like path in this graph, which means minimizing the number of blocks is the same as splitting this graph into the minimum number of paths that do not intersect at the vertices. This is a fairly well-known task, for example here is described its solution. $$$\newline$$$ However, the authors of the problem propose a slightly different, much simpler solution: iterate through the boxes in descending order $$$a_i$$$, maintaining the current set of blocks, for each of which we store the size of the last nested box, and try to greedily nest the current box in some block. If you can't put it anywhere, then make a new block consisting only of this box. $$$\newline$$$ This solution intuitively seems incorrect to me, but I couldn't come up with a countertest. In addition, if this greed works, any problem of covering a graph with paths can be reduced to the problem of boxes, after which it can be solved for $$$O(n\log n)$$$ instead of a long solution with matching (and this is some kind of nonsense). I would be grateful if someone could tell me what the problem of this greed is and lead a countertest to it.