Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

New answers tagged


Your problem is the same as interval graph coloring. There is a well-known greedy algorithm solving the problem optimally, running in linear time if the intervals are already sorted.


I'm assuming that $W$ is an integer upper bound to $\sum_i w_i$, as asked by xskxzr, that all $w_i$ are positive integers, and that the values $w$ in the queries are also integers upper bounded by $W$. For $i \ge 1$, let $S[i,w]$ be the largest index $j \in \{1, \dots, i\}$ such that it is possible to select a subset of $\{w_k : j \le k \le i \}$ of weight ...

Top 50 recent answers are included