An independent d-division
Think about what happens when you manage to find the first interval, say it is $[v_1,...,v_k]$ for some $k$. Then what would you be able to say about the minimal division of $v_{k+1},...,v_n?$
Think also about how you could find the first interval. Starting from an empty interval and expanding it (how?) should do the trick.