needs and a list of ranges ranges, where ranges[j] = [l, r]. Each range lets you lower by 1 any cells with indices from l to r inclusive; you decide separately for each cell whether to lower it. The order of the ranges does not matter.
The goal is an array of all zeros. Some ranges may be thrown away up front. Return the largest number of ranges you can throw away while the remaining ones are still enough. If even all the ranges are not enough, return -1.needs=[1, 0, 1], ranges=[[0, 2], [0, 0], [2, 2], [1, 1]] → 3
The range [0, 2] alone is enough: it takes one from cells 0 and 2 and leaves cell 1 alone. The other three ranges are spare.
needs=[2, 1], ranges=[[0, 1], [1, 1], [0, 0]] → 1
Cell 0 needs both ranges that cover it, [0, 1] and [0, 0]. The first one also clears cell 1, so [1, 1] can be dropped.
needs=[0, 3], ranges=[[1, 1], [0, 1]] → -1
Only two ranges cover cell 1, but it needs three.
needs=[1, 0, 1], ranges=[[0, 2], [0, 0], [2, 2], [1, 1]]
3
Run checks the first 3 tests in your browser. Submit checks all 109 tests on the server, hidden ones included.