You are given a **0-indexed** 2D integer array `brackets`

where `brackets[i] = [upper`

means that the _{i}, percent_{i}]`i`

tax bracket has an upper bound of ^{th}`upper`

and is taxed at a rate of _{i}`percent`

. The brackets are _{i}**sorted** by upper bound (i.e. `upper`

for _{i-1} < upper_{i}`0 < i < brackets.length`

).

Tax is calculated as follows:

- The first
`upper`

dollars earned are taxed at a rate of_{0}`percent`

._{0} - The next
`upper`

dollars earned are taxed at a rate of_{1}- upper_{0}`percent`

._{1} - The next
`upper`

dollars earned are taxed at a rate of_{2}- upper_{1}`percent`

._{2} - And so on.

You are given an integer `income`

representing the amount of money you earned. Return *the amount of money that you have to pay in taxes.* Answers within `10`

of the actual answer will be accepted.^{-5}

**Example 1:**

Input:brackets = [[3,50],[7,10],[12,25]], income = 10Output:2.65000Explanation:The first 3 dollars you earn are taxed at 50%. You have to pay $3 * 50% = $1.50 dollars in taxes. The next 7 - 3 = 4 dollars you earn are taxed at 10%. You have to pay $4 * 10% = $0.40 dollars in taxes. The final 10 - 7 = 3 dollars you earn are taxed at 25%. You have to pay $3 * 25% = $0.75 dollars in taxes. You have to pay a total of $1.50 + $0.40 + $0.75 = $2.65 dollars in taxes.

**Example 2:**

Input:brackets = [[1,0],[4,25],[5,50]], income = 2Output:0.25000Explanation:The first dollar you earn is taxed at 0%. You have to pay $1 * 0% = $0 dollars in taxes. The second dollar you earn is taxed at 25%. You have to pay $1 * 25% = $0.25 dollars in taxes. You have to pay a total of $0 + $0.25 = $0.25 dollars in taxes.

**Example 3:**

Input:brackets = [[2,50]], income = 0Output:0.00000Explanation:You have no income to tax, so you have to pay a total of $0 dollars in taxes.

**Constraints:**

`1 <= brackets.length <= 100`

`1 <= upper`

_{i}<= 1000`0 <= percent`

_{i}<= 100`0 <= income <= 1000`

`upper`

is sorted in ascending order._{i}- All the values of
`upper`

are_{i}**unique**. - The upper bound of the last tax bracket is greater than or equal to
`income`

.

**Solution: Follow the rules**

“Nothing is certain except death and taxes” – Benjamin Franklin

Time complexity: O(n)

Space complexity: O(1)

## C++

1 2 3 4 5 6 7 8 9 10 11 12 |
// Author: Huahua class Solution { public: double calculateTax(vector<vector<int>>& A, int income) { double ans = 0; for (int i = 0; i < A.size(); ++i) { ans += (min(income, A[i][0]) - (i ? A[i-1][0] : 0)) * A[i][1] / 100.0; if (A[i][0] >= income) break; } return ans; } }; |