Решая курс по подготовке к выпускным экзаменам, я столкнулся со следующей задачей: $$$\newline$$$ Даны $$$n$$$ коробок, каждая длиной $$$a_i$$$. Мы можем вкладывать одну коробку в другую, если размер внутренней хотя бы на 7 единиц меньше внешней, при этом в каждую коробку не могла быть вложена только одна другая, а также какждая коробка может быть вложена максимум в одну другую. Множество коробок, вложенных друг в друга, назовем блоком. В задаче просят расположить коробки так, чтобы минимизировать количество блоков. $$$\newline$$$ Очевидно, данную задачу можно решать следующим образом (и это решение точно будет правильным): строим граф, в котором будет ребро $$$i \rightarrow j$$$, если $$$a_i - 7 \ge a_j$$$, данный граф очевидно не будет иметь циклов. Теперь блок из вложенных друг в друга коробок будет выглядеть как какой-то путь в данном графе, значит, минимизировать количество блоков, это то же самое, что разбить данный граф на минимальное количество непересекающихся по вершинам путей. Это довольно известная задача, например тут описывается ее решение. $$$\newline$$$ Тем не менее, авторы задачи предлагают несколько другое, гораздо более простое решение: перебирать коробки по убыванию $$$a_i$$$, поддерживая текущее множество блоков, для каждого из которых храним размер последней вложенной коробки, и пытаться жадно вложить текущую коробку в какой-нибудь блок. Если вложить никуда нельзя, то сделать новый блок, состоящий только из этой коробки. $$$\newline$$$ Данное решение интуитивно кажется мне некорректным, однако контртест я не смог придумать. К тому же, если данный жадник работает, любую задачу о покрытии графа путями можно сводить к задаче о коробках, после чего решать ее за $$$O(n \log n)$$$ вместо долгого решения паросочетаниями (а это бред какой-то). Буду благодарен, если кто-то подскажет, в чем проблема данного жадника и приведет контртест к нему.