# LeetCode Maximum Performance of a Team

There are n engineers numbered from 1 to n and two arrays: speed and efficiency, where speed[i] and efficiency[i] represent the speed and efficiency for the i-th engineer respectively. Return the maximum performance of a team composed of at most k engineers, since the answer can be a huge number, return this modulo 10^9 + 7.

The performance of a team is the sum of their engineers’ speeds multiplied by the minimum efficiency among their engineers.

Example 1:

Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 2
Output: 60
Explanation:
We have the maximum performance of the team by selecting engineer 2 (with speed=10 and efficiency=4) and engineer 5 (with speed=5 and efficiency=7). That is, performance = (10 + 5) * min(4, 7) = 60.


Example 2:

Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 3
Output: 68
Explanation:
This is the same example as the first but k = 3. We can select engineer 1, engineer 2 and engineer 5 to get the maximum performance of the team. That is, performance = (2 + 10 + 5) * min(5, 4, 7) = 68.


Example 3:

Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 4
Output: 72


Constraints:

• 1 <= n <= 10^5
• speed.length == n
• efficiency.length == n
• 1 <= speed[i] <= 10^5
• 1 <= efficiency[i] <= 10^8
• 1 <= k <= n

class Solution {
public:
int maxPerformance(int n, vector<int>& speed, vector<int>& efficiency, int k) {
vector<pair<int, int>> workers;
for (int i = 0; i < n; ++i) {
workers.push_back(make_pair(efficiency[i], speed[i]));
}
sort(workers.begin(), workers.end()); // 默认对pair.first升序排列
priority_queue <int, vector<int>, greater<int> > pq; // pq默认是最大堆，这是构建最小堆
long long ans = 0;
long long sum_speed = 0;
for (int i = n - 1; i >= 0; --i) {
sum_speed += workers[i].second;
pq.push(workers[i].second);
if (pq.size() > k) {
sum_speed -= pq.top();
pq.pop();
}
ans = max(ans, sum_speed*workers[i].first);
}
return ans % (int)(1e9 + 7);
}
};

Design a simplified version of Twitter where users can post tweets, follow/unfollow another user and is able to see the 10 most recent tweets in the user’s news feed. Your design should support the following methods:
1. postTweet(userId, tweetId): Compose a new tweet.
2. getNewsFeed(userId): Retrieve the 10 most recent tweet ids in the user’s news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent.
3. follow(followerId, followeeId): Follower follows a followee.
4. unfollow(followerId, followeeId): Follower unfollows a followee.
Example:
Twitter twitter = new Twitter();
// User 1 posts a new tweet (id = 5).
// User 1's news feed should return a list with 1 tweet id -> [5].
// User 1 follows user 2.
// User 2 posts a new tweet (id = 6).
// User 1's news feed should return a list with 2 tweet ids -> [6, 5].
// Tweet id 6 should precede tweet id 5 because it is posted after tweet id 5.
// User 1 unfollows user 2.
// User 1's news feed should return a list with 1 tweet id -> [5],
// since user 1 is no longer following user 2.


# LeetCode Smallest Range

LeetCode Smallest Range You have k lists of sorted integers in ascending order. Find the smallest range that includes at least one number from each of the k lists. We define the range [a,b] is smaller than range [c language=",d"][/c] if b-a < d-c or a < c if b-a == d-c. Example 1:

Input:[[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
Output: [20,24]
Explanation:
List 1: [4, 10, 15, 24,26], 24 is in range [20,24].
List 2: [0, 9, 12, 20], 20 is in range [20,24].
List 3: [5, 18, 22, 30], 22 is in range [20,24].

Note:
1. The given list may contain duplicates, so ascending order means >= here.
2. 1 <= k <= 3500
3. -105 <= value of elements <= 105.
4. For Java users, please note that the input type has been changed to List<List<Integer>>. And after you reset the code template, you’ll see this point.

1. i,j,k分别指向三个数组的开头，即i=j=k=0，相当于在[4,0,5]中找最大值和最小值，构成区间[0,5]，长度为5。
2. 最小值为j所在数组，所以++j，在新的数组[4,9,5]中找最大值和最小值，构成区间[4,9]，长度为5。
3. 最小值为i所在数组，所以++i，在新的数组[10,9,5]中找最大值和最小值，构成区间[5,10]，长度为5。
4. ++k，新数组[10,9,18]，区间[9,18]，长度为9。
5. ++j，新数组[10,12,18]，区间[10,18]，长度为8。
6. ++i，新数组[15,12,18]，区间[12,18]，长度为6。
7. ++j，新数组[15,20,18]，区间[15,20]，长度为5。
8. ++i，新数组[24,20,18]，区间[18,24]，长度为6。
9. ++k，新数组[24,20,22]，区间[20,24]，长度为4。
10. ++j，第二个数组遍历完毕，结束，遍历过程中，得到的长度最短的区间是[20,24]。

# LeetCode Course Schedule III

LeetCode Course Schedule III There are n different online courses numbered from 1 to n. Each course has some duration(course length) t and closed on dth day. A course should be taken continuously for t days and must be finished before or on the dth day. You will start at the 1st day. Given n online courses represented by pairs (t,d), your task is to find the maximal number of courses that can be taken. Example:

Input: [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]
Output: 3
Explanation:
There're totally 4 courses, but you can take 3 courses at most:
First, take the 1st course, it costs 100 days so you will finish it on the 100th day, and ready to take the next course on the 101st day.
Second, take the 3rd course, it costs 1000 days so you will finish it on the 1100th day, and ready to take the next course on the 1101st day.
Third, take the 2nd course, it costs 200 days so you will finish it on the 1300th day.
The 4th course cannot be taken now, since you will finish it on the 3300th day, which exceeds the closed date.

Note:
1. The integer 1 <= d, t, n <= 10,000.
2. You can’t take two courses simultaneously.

1. 选修第一门课程，now=3<8，优先队列堆顶为3
2. 选修第二门课程，now=3+7=10<=10，优先队列堆顶为7
3. 选修第三门课程，now=10+5=15>14，失败；发现堆顶课程的持续时间是7，大于当前课程的持续时间5，所以可以把堆顶课程换成该门课程，则新的now=10-7+5=8，堆顶为5。因为该门课程的持续时间比堆顶短，且关闭时间已排序，所以大于堆顶的关闭时间，所以把堆顶课程换成该课程，该课程肯定能过完成。且新的now=8比先前的now=10要小，使得可以完成第四门课程。
4. 选修第四门课，now=8+8=16<17，优先队列为8。

LeetCode Task Scheduler Given a char array representing tasks CPU need to do. It contains capital letters A to Z where different letters represent different tasks.Tasks could be done without original order. Each task could be done in one interval. For each interval, CPU could finish one task or just be idle. However, there is a non-negative cooling interval n that means between two same tasks, there must be at least n intervals that CPU are doing different tasks or just be idle. You need to return the least number of intervals the CPU will take to finish all the given tasks. Example 1:

Input: tasks = ['A','A','A','B','B','B'], n = 2
Output: 8
Explanation: A -> B -> idle -> A -> B -> idle -> A -> B.

Note:
1. The number of tasks is in the range [1, 10000].

CPU需要处理一系列任务，限制条件是两个相同的任务被处理的时间至少需要间隔n时刻，问CPU最少需要多长时间能处理完所有任务。 比赛没做出来，参考讨论区。 根据题意，两个任务被处理至少需要间隔n时刻，所以我们可以认为CPU处理一批任务的循环周期是n+1，比如0时刻处理了任务’A’，则至少要到n+1时刻才能再次处理任务’A’，中间间隔了n时刻。 假设数量最多的任务的数量是k，则我们至少需要k个周期才能把这个任务处理完。为了让CPU处理的空闲时间更少，我们在一个周期内尽量让CPU处理的任务更丰富。所以想象一下，我们有k个桶，相当于k个周期，每个周期，我们把频率最高的任务拿出来，分发到这最多k个桶中。如果所有不同任务都分发完了还没有填满一个桶，则说明该桶内（周期内）CPU需要空闲等待。 比如样例中，最高频的任务是A和B，都是3，所以我们至少需要3个桶。每个桶的容量是n+1=3，相当于相同任务的距离是3。每次我们把A和B扔到不同的桶中，前两个桶各有一个空闲等待，第三个桶因为结束了，所以不需等待。 因为每次都需要取出最高频的任务去分发，所以用一个优先队列来实时更新频率排名。 完整代码如下： [cpp] class Solution { public: int leastInterval(vector<char>& tasks, int n) { map<char, int> count; for (const auto& c : tasks)++count[c]; priority_queue<pair<int, char>> pq; for (const auto& p : count)pq.push({ p.second,p.first }); int cycle = n + 1, time = 0; while (!pq.empty()) { vector<pair<int, char>> tmp; int tsk = 0; for (int i = 0; i < cycle; ++i) { if (!pq.empty()) { tmp.push_back(pq.top()); pq.pop(); ++tsk; } } for (auto& t : tmp) { if (–t.first) { pq.push(t); } } time += pq.empty() ? tsk : cycle; } return time; } }; [/cpp] 本代码提交AC，用时95MS。]]>

# LeetCode Find K Pairs with Smallest Sums

LeetCode Find K Pairs with Smallest Sums You are given two integer arrays nums1 and nums2 sorted in ascending order and an integer k. Define a pair (u,v) which consists of one element from the first array and one element from the second array. Find the k pairs (u1,v1),(u2,v2) …(uk,vk) with the smallest sums. Example 1:

Given nums1 = [1,7,11], nums2 = [2,4,6],  k = 3
Return: [1,2],[1,4],[1,6]
The first 3 pairs are returned from the sequence:
[1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]

Example 2:
Given nums1 = [1,1,2], nums2 = [1,2,3],  k = 2
Return: [1,1],[1,1]
The first 2 pairs are returned from the sequence:
[1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]

Example 3:
Given nums1 = [1,2], nums2 = [3],  k = 3
Return: [1,3],[2,3]
All possible pairs are returned from the sequence:
[1,3],[2,3]