Блог пользователя Snapper_001

Range Concatination With Min Cost
Автор Snapper_001, история, 2 года назад, По-английски

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

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить