1. Profitable Project Pairs
In a tech company, there are n projects available for the team to work on. Due to resource constraints, they can only work on any two of the projects. The expected profits for each project are provided in the array profit, while the implementation costs are given in the array implementationCost.
The task is to determine the number of pairs of projects that can be chosen from the available options such that the company earns a profit after implementing both projects.
That is, two projects indexed i and j are chosen if (profit[i] - implementationCost[i]) + (profit[j] - implementationCost[j]) > 0, where 0 <= i < j < n.
Function Description
Complete the function getProfitablePairs in the editor below.
getProfitablePairs takes the following parameter(s):
int profit[n]: the profit earned by the company from each projectint implementationCost[n]: the cost of implementing each project
Returns
long: the number of pairs of projects that are profitable
Constraints
1 <= n <= 2 * 10^51 <= profit[i], implementationCost[i] <= 10^9
这题先把每个项目转成净收益 net = profit[i] – implementationCost[i]，然后问题就变成统计有多少对下标 (i, j) 满足 net[i] + net[j] > 0。由于 n 可达 2e5，不能直接枚举所有 O(n^2) 对；更合适的做法是先排序所有净收益，再对每个数用双指针或二分找出能与它配对的“最小可行右边界”，从而在 O(n log n) 内统计答案。样例中本质上就是找出那些两项净收益之和为正的项目对。
