Snapper_001's blog

Range Concatination With Min Cost
By Snapper_001, history, 3 years ago, In English

Given the m ranges that denotes subarray of an array of length n i --> [l ,r] 1<=l<=r<=n Cost of Concatination of two ranges is 1 Find the min cost to overlap the whole array or return -1 if not exist

1<=n<=100

Plz help. Thanks in advance

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If I understood correctly, you can concatenate two overlapping ranges: concat([1, 4], [3, 6]) = [1,6]. Then I have this solution:

  1. set l_res = 1; n_iter = 0.
  2. iterate over ranges: find the range with maximum r over all ranges that satisfy l <= l_res. If you can't do that, then the answer is -1. (Also check that r > l_res for n_iter >= 1; r >= l_res for n_iter==0).
  3. set l_res to r; increase n_iter by 1; if l_res == n then return n_iter. If not, return to step 2.

Complexity is O(n^2); can be reduced to O(n*log n) if you sort the ranges.

→ Reply