Woodcutters Problem

Woodcutters Problem — ExecCode Medium DSA Practice

Solve the Woodcutters problem on ExecCode. Free online medium DSA practice in DP. Write and run code in Java, C++, Python — no signup required to run.

Problem description

Trees stand on a line at strictly increasing positions x, with heights h. A cut tree falls left onto [x - h, x] or right onto [x, x + h]. It may also be left standing. A fallen tree may not touch another tree or another fallen tree. Return the maximum number of trees that can be cut. You are given: x — positions from left to right h — height of each tree Return the maximum number of cut trees. The first tree can always fall left, and the last tree can always fall right. For each middle tree, prefer falling left when that segment ends before the space already used. Otherwise fall right when the segment ends before the next tree.

Examples

Input {'x': [1, 2, 5, 10, 19], 'h': [2, 1, 10, 9, 1]}; Output 3. Input {'x': [1, 10, 20], 'h': [1, 1, 1]}; Output 3. Input {'x': [1], 'h': [5]}; Output 1

Constraints

1 <= x.length <= 100000 h.length == x.length 1 <= h[i] <= 1000000000 x is strictly increasing and each position fits in a signed 64-bit integer

Practice Woodcutters free on ExecCode. Browse DSA problems, topic map, and placement guides.