1187-make-array-strictly-increasing.rb

# frozen_string_literal: true

# https://leetcode.com/problems/make-array-strictly-increasing
# 1187. Make Array Strictly Increasing
# Hard

=begin
Given two integer arrays arr1 and arr2, return the minimum number of operations (possibly zero) needed to make arr1 strictly increasing.

In one operation, you can choose two indices 0 <= i < arr1.length and 0 <= j < arr2.length and do the assignment arr1[i] = arr2[j].

If there is no way to make arr1 strictly increasing, return -1.

Example 1:
Input: arr1 = [1,5,3,6,7], arr2 = [1,3,2,4]
Output: 1
Explanation: Replace 5 with 2, then arr1 = [1, 2, 3, 6, 7].

Example 2:
Input: arr1 = [1,5,3,6,7], arr2 = [4,3,1]
Output: 2
Explanation: Replace 5 with 3 and then replace 3 with 4. arr1 = [1, 3, 4, 6, 7].

Example 3:
Input: arr1 = [1,5,3,6,7], arr2 = [1,6,3,3]
Output: -1
Explanation: You can't make arr1 strictly increasing.

Constraints:
* 1 <= arr1.length, arr2.length <= 2000
* 0 <= arr1[i], arr2[i] <= 10^9
=end

# @param {Integer[]} arr1
# @param {Integer[]} arr2
# @return {Integer}
defmake_array_increasing(arr1,arr2)
@arr1=arr1
@arr2=arr2.uniq.sort
@memo={}

res=swaps(0, -1)
res == Float::INFINITY ? -1 : res
end

defswaps(i,val)
return0ifi == @arr1.length
return@memo[[i,val]]if@memo[[i,val]]

options=[]

if@arr1[i] > val
options << swaps(i + 1,@arr1[i])
end

j=@arr2.bsearch_index{ |num| num > val}

options << (j ? swaps(i + 1,@arr2[j]) + 1 : Float::INFINITY)

@memo[[i,val]]=options.min
end

# **************** #
# TEST #
# **************** #

require"test/unit"
classTest_make_array_increasing < Test::Unit::TestCase
deftest_
assert_equal1,make_array_increasing([1,5,3,6,7],[1,3,2,4])
assert_equal2,make_array_increasing([1,5,3,6,7],[4,3,1])
assert_equal(-1,make_array_increasing([1,5,3,6,7],[1,6,3,3]))
end
end