Minimum swaps to make sequences increasing

Problem Statement

"Minimum swaps to make sequences increasing" states that you are given two arrays a and b of the same size n. Swap the elements of the array a with array b to make both arrays strictly increasing. You can swap elements at the same indexes only i.e. a can be swapped with b only. So we need to find the minimum number of swaps that are required to make both arrays a and b strictly increasing. Print -1 if no answer exists.

Example

 

a = {2, 3, 7, 5}

 

b = {1, 2, 4, 11}

1

Explanation: We can swap the third element in a with the third element in b, which will make both the arrays strictly increasing.

a = {1, 2, 5, 4, 9, 8}

 

b = {1, 2, 3, 6, 7, 11}

2

Explanation; Since we swapped the 5th element. Both the arrays are now arranged in strictly increasing order.

a = {2, 1}

 

b = {1, 2}

-1

 

Explanation: Because there is no way to swap the elements of the array a with b such that they get arranged in strictly increasing order. So, we return -1 as an answer.

Approach

Algorithm for Minimum swaps to make sequences increasing problem

1. Initialize two nonempty arrays a and b of the integer type and of the same size n.

2. Similarly, initialize an integer variable count as 0.

3. Traverse through the array elements starting from 1 till n-1.

4.

 

www.tutorialcup.com/cplusplus/minimum-swaps-to-make-seque...

Done