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
A clean way to solve this is to convert each project into its net profit, `profit[i] – implementationCost[i]`, and then count pairs whose sum is positive. Since `n` can be as large as `2 * 10^5`, an `O(n^2)` brute-force approach is too slow. Instead, sort the net profits and use a two-pointer or binary-search-based counting method to accumulate the number of valid pairs in `O(n log n)` time. The sample illustrates exactly this idea by enumerating the profitable project pairs.
