Наложенные графики акций
Задача по программированию с проверкой онлайн
- Сложность
- Сложная
- Языки
- Python
- JavaScript
- TypeScript
- Java
- Go
- Темы
- Деревья и графы
- Матрицы и сетки
Дан список prices: для каждой из n акций — её цены в одни и те же k моментов времени. График акции — ломаная через точки (0, prices[i][0]), (1, prices[i][1]), …, (k − 1, prices[i][k − 1]).
Несколько графиков можно нарисовать на одной общей диаграмме, только если никакие две их ломаные не пересекаются и не касаются. Две ломаные этому условию удовлетворяют ровно тогда, когда одна из акций строго дороже другой в каждый из k моментов. Верните наименьшее число диаграмм, на которых можно показать все акции (каждая акция — ровно на одной).
Ограничения: 1 ≤ n ≤ 100, 1 ≤ k ≤ 25, цены от 0 до 1 000 000.
Пример: [[1, 2, 3, 4], [2, 3, 4, 6], [6, 5, 4, 3]] → 2.
Источник: Coding Competitions Archive, codejam/2009/round_2/stock_charts · © Google LLC · Apache-2.0 · условие переведено и дополнено