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

3

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.


1

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