The basic idea behind my approach is to process the intervals in increasing order of start times, keeping track of the earliest end time for any task so far (this is the latest visit that covers all considered tasks). When you encounter a task that begins after that latest possible visit, then you store the visit and start processing the next batch of tasks.
While this is not asymptotically better than the solution in the book in time or space, the only additional storage is the result array. One could make the argument that a tight bound of O(v) space, where v is the number of visits, is better than the O(n) space used in the book given that k <= n. However, my solution also makes the choice to sort the input array directly, which is not always practical (without which, it would be the same O(n) additional space).
I still find it worth sharing for academic curiosity.
vector FindMinimumVisits(vector* tasks) {
if (tasks->empty()) return { };
sort(tasks->begin(), tasks->end(), IntervalCompare());
int next_right = tasks->front().right;
vector<int> visits;
for (const auto& task : *tasks) {
if (task.left > next_right) {
visits.push_back(next_right);
next_right = task.right;
} else {
next_right = min(next_right, task.right);
}
}
visits.push_back(next_right);
return visits;
}