Editing 2016 Jan Platinum Problem 2 Mowing the Field (section)

== Solution ==

The key insight is that if Farmer John has the choice between mowing two cells, he should always mow the one that he will not pass again first. This is because any cell that Farmer John passes but does not mow will grow one additional unit of grass, increasing the time it takes to mow that cell.

We can maintain a priority queue of cells to mow, sorted by the latest time that Farmer John can mow a cell without having to wait for the grass to grow. For each cell, we calculate this time as the maximum of the current time and the time at which Farmer John will next pass the cell. We can find the latter by using a stack of cells that Farmer John has not yet mowed.

Then, we repeatedly take the cell with the earliest latest mow time from the priority queue and mow it, updating the current time accordingly. After mowing a cell, we remove it from the stack. If the stack is not empty, then we update the latest mow time of the cell at the top of the stack.

This algorithm runs in O(N log N) time, which is sufficient to pass all test cases.