3027. Find the Number of Ways to Place People II

Leetcode link

题目简介

这一题跟 3025 唯一的差别就是把参数的范围提高了，所以对算法复杂度的要求理论上会更高，但我们之前的算法复杂度已经是 O(n^2) 了，所以直接套用就好

解题思路

直接套用 3025 的代码

Javascript

/**
 * @param {number[][]} points
 * @return {number}
 */
var numberOfPairs = function(points) {
    points.sort((a, b) => {
        if (a[0] === b[0]) {
            return b[1] - a[1]
        }
        return a[0] - b[0]
    })

    let count = 0
    const n = points.length

    for (let i = 0; i < n; i++) {
        const upperYLimit = points[i][1]
        let lowerYLimit = Number.MIN_SAFE_INTEGER

        for (let j = i + 1; j < n; j++) {
            const curY = points[j][1]
            if(curY <= upperYLimit && curY > lowerYLimit) {
                count++
                lowerYLimit = curY

                if(curY === upperYLimit) {
                    break
                }
            }
        }
    }

    return count
};