Variant of interval scheduling with varying task durations
The deterministic version of your problem (i.e. to determine whether there is a valid arrangement) is strongly NP-complete by a reduction from 3-Partition, as suggested in [1]. 

Given an instance $x_1,x_2,\ldots,x_{3m}$ of 3-Partition, let the duration in your problem be $[0, mB+m]$ where $B=\sum_{i=1}^{3m} x_i/m$. For each element $x_i$, there is a task with duration $x_i$. The intervals for these tasks are all $[0, mB+m]$. In addition, there are additionally $m$ tasks with duration $1$, and their intervals are respectively $[B, B+1], [2B+1, 2B+2],\ldots,[mB+m-1,mB+m]$. Note the positions of these additional tasks are fixed.

Since we can assume $B/4&lt;x_i&lt;B/2$ for all $i$ in 3-Partition, we can see there is a valid partition if and only if there is a valid arrangement in your problem. 



[1] Garey, M. R., &amp; Johnson, D. S. (1977). Two-processor scheduling with start-times and deadlines. SIAM Journal on Computing, 6(3), 416-426.