## 801. Minimum Swaps To Make Sequences Increasing

We have two integer sequences `A` and `B` of the same non-zero length.

We are allowed to swap elements `A[i]` and `B[i]`.  Note that both elements are in the same index position in their respective sequences.

At the end of some number of swaps, `A` and `B` are both strictly increasing.  (A sequence is strictly increasing if and only if `A < A < A < ... < A[A.length - 1]`.)

Given A and B, return the minimum number of swaps to make both sequences strictly increasing.  It is guaranteed that the given input always makes it possible.

```Example:
Input: A = [1,3,5,4], B = [1,2,3,7]
Output: 1
Explanation:
Swap A and B.  Then the sequences are:
A = [1, 3, 5, 7] and B = [1, 2, 3, 4]
which are both strictly increasing.
```

Note:

• `A, B` are arrays with the same length, and that length will be in the range `[1, 1000]`.
• `A[i], B[i]` are integer values in the range `[0, 2000]`.

## Rust Solution

``````struct Solution;

impl Solution {
fn min_swap(a: Vec<i32>, b: Vec<i32>) -> i32 {
let n = a.len();
let mut keep = vec![n; n];
let mut swap = vec![n; n];
keep = 0;
swap = 1;
for i in 1..n {
if a[i - 1] < a[i] && b[i - 1] < b[i] {
keep[i] = keep[i - 1];
swap[i] = swap[i - 1] + 1;
}
if a[i - 1] < b[i] && b[i - 1] < a[i] {
keep[i] = keep[i].min(swap[i - 1]);
swap[i] = swap[i].min(keep[i - 1] + 1);
}
}
swap[n - 1].min(keep[n - 1]) as i32
}
}

#[test]
fn test() {
let a = vec![1, 3, 5, 4];
let b = vec![1, 2, 3, 7];
let res = 1;
assert_eq!(Solution::min_swap(a, b), res);
}
``````

Having problems with this solution? Click here to submit an issue on github.