黑白点的最大匹配数目 – JS

黑白点的最大匹配数目

[描述]
--------------------------------------------------------------------------------------
设B = {b1, b2, …, bn} 和 W = {w1, w2, …, wn}分别为平面上黑点和白点的两个集合。
一黑点bi = (xi, yi) 与一白点wj = (xj, yj)
匹配当且仅当 xi <= xj 和 yi <= yj 同时成立，
每个点最多只能用于一次匹配，
请找出黑白点之间的最大匹配数目。
黑点和白点各自的数量均不超过100000；
平面为(0, 0)到(10000, 10000)的矩形中的整数点
黑点白点坐标可能相同，B集合、W集合中也可能包含相同的元素。
--------------------------------------------------------------------------------------

[输入]
--------------------------------------------------------------------------------------
输入的第一行包括一个整数T (1 <= T <= 10)，表示有T组测试数据.
对于每组测试数据：
第一行两个整数，n(黑点个数) m(白点个数)，0 < n, m <= 100000
接下来n行每行有两个整数并用空格隔开：
黑点的横坐标x   黑点的纵坐标y
再接下来m行每行有两个整数同样用空格隔开：
白点的横坐标x   白点的纵坐标y
--------------------------------------------------------------------------------------

[输出]
--------------------------------------------------------------------------------------
对于每组测试数据，输出一行一个整数，表示最大匹配数。
--------------------------------------------------------------------------------------

[样例输入]
--------------------------------------------------------------------------------------
2
2 2
1 0
0 1
1 1
0 0
1 1
1 1
0 0
--------------------------------------------------------------------------------------

[样例输出]
--------------------------------------------------------------------------------------
1
0
--------------------------------------------------------------------------------------

[答案提示]
第一组中选择黑点（1，0）可以和白点（1，1）匹配，匹配数为1。
任何其他方式匹配都不能达到匹配数为2，所以答案为1。

第二组中黑点和白点不满足x、y的相对关系，没法配对，答案为0。

/*========================================================
// 来源: cnblogs
// 作者: Tong Zeng
// Javascript 随机数函数 学习之一：产生服从均匀分布随机数
// https://www.cnblogs.com/zztt/p/4024906.html
==========================================================*/
// [min, max]
let randomMinAndMax = (min, max) => {
  return Math.floor(Math.random() * (max - min + 1)) + min;
}

// [min , max)
let randomMinOffMax = (min, max) => {
  return Math.floor(Math.random() * (max - min)) + min;
}

// (min, max]
let randomOffMinMax = (min, max) => {
  return Math.ceil(Math.random() * (max - min )) + min;
}

/*========================================================
// 来源: csdn
// 作者: SundayAaron
// js生成不重复的随机数
// https://blog.csdn.net/SundayAaron/article/details/80181380
==========================================================*/
let randomIntegerArr = (minNum, maxNum, len) => {
  if (maxNum > minNum) {
    let [i, setArr, result, diffLen] = [minNum, [], [], maxNum - minNum];

    while (i < maxNum) {
      setArr.push(i);
      i++;
    }
    // 随机出现一次
    setArr.sort(() => {
      return 0.5 - Math.random();
    });

    // 均匀输出
    i = 0;
    while (i < len) {
      result.push(setArr[randomMinOffMax(0, diffLen)]);
      i++;
    };

    return result;
  } else {
    return;
  }
};

/*========================================================
// 黑白点计算
// [运行时间限制]: 未考虑
// [内存限制]: 未考虑
==========================================================*/
function getBWMatchCount(input) {
  let inputArray = input.split('\n');
  let testTotal = +(inputArray.splice(0, 1));

  while (testTotal > 0) {
    let nmArray = inputArray.splice(0, 1)[0].split(' ');
    let count = 0;
    let BW = [];
    let bTree = [];

    // 黑点
    inputArray.splice(0, +nmArray[0]).forEach(node => {
      node = node.split(' ');
      BW.push({
        x: +(node[0]),
        y: +(node[1]),
        color: 1
      });
    });

    // 白点
    inputArray.splice(0, +nmArray[1]).forEach(node => {
      node = node.split(' ');
      BW.push({
        x: +(node[0]),
        y: +(node[1]),
        color: 0
      });
    });

    BW.sort((a, b) => {
      if (a.x != b.x) {
        /**
         * > 0: b,a;
         * < 0: a,b;
         */
        return a.x - b.x; // 
      } else {
        /**
         * x坐标相同，黑点在前
         * 1: 黑点 
         * 0: 白点
         * 需要 a,b 排序的话, 需要负数 
         */
        return -(a.color - b.color);
      }
    });

    BW.forEach((node) => {
      if (node.color === 1) {
        // 黑点
        bTree.push(node.y);
      } else {
        // 白点
        let len = bTree.length;
        bTree.sort((a, b) => {
          return a - b;
        });
        if (len > 0 && bTree[0] <= node.y) {
          let i = 1;
          for (; i < len; i++) {
            if (bTree[i] > node.y) {
              break;
            }
          }
          // 移除 黑点集合中, y最大的小于白点y值的 黑点 
          bTree.splice(i - 1, 1);
          count++;
        }
      }
    });
    console.log(count);

    nmArray = null;
    BW = null;
    bTree = null;
    count = null;
    testTotal--;
  }
}