870. Advantage Shuffle

Given two arrays A and B of equal size, the advantage of A with respect to B is the number of indices i for which A[i] > B[i].

Return any permutation of A that maximizes its advantage with respect to B.

 

Example 1:

Input: A = [2,7,11,15], B = [1,10,4,11]
Output: [2,11,7,15]

Example 2:

Input: A = [12,24,8,32], B = [13,25,32,11]
Output: [24,32,8,12]

 

Note:

  1. 1 <= A.length = B.length <= 10000
  2. 0 <= A[i] <= 10^9
  3. 0 <= B[i] <= 10^9

Rust Solution

struct Solution;

type Pair = (usize, i32);

impl Solution {
    fn advantage_count(mut a: Vec<i32>, b: Vec<i32>) -> Vec<i32> {
        let n = a.len();
        let mut b: Vec<Pair> = b.into_iter().enumerate().collect();
        let mut l = 0;
        let mut r = n - 1;
        a.sort_unstable();
        b.sort_unstable_by_key(|p| p.1);
        let mut res: Vec<i32> = vec![0; n];
        for i in 0..n {
            if a[i] <= b[l].1 {
                res[b[r].0] = a[i];
                r -= 1;
            } else {
                res[b[l].0] = a[i];
                l += 1;
            }
        }
        res
    }
}

#[test]
fn test() {
    let a = vec![2, 7, 11, 15];
    let b = vec![1, 10, 4, 11];
    let res = vec![2, 11, 7, 15];
    assert_eq!(Solution::advantage_count(a, b), res);
    let a = vec![12, 24, 8, 32];
    let b = vec![13, 25, 32, 11];
    let res = vec![24, 32, 8, 12];
    assert_eq!(Solution::advantage_count(a, b), res);
}

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