# 貪欲法(Greedy algorithm)で問題を解く

c++algorithm

## Best Time to Buy and Sell Stock II - LeetCode

Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).

Example 1:
Input: [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.

class Solution {
public:
int maxProfit(vector<int>& prices) {
if (prices.size() <= 1) {
return 0;
}
int ret = 0;
int buyidx = 0;
for (int i = 1; i < prices.size(); i++) {
if (prices[i] >= prices[i-1]) {
continue;
}
ret += prices[i-1] - prices[buyidx];
buyidx = i;
}
ret += prices[prices.size()-1] - prices[buyidx];
return ret;
}
};

Wiggle Subsequence - LeetCodeも同様に解ける。

## Jump Game - LeetCode

Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.

Example 1:
Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

class Solution {
public:
bool canJump(vector<int>& nums) {
int pos = nums.size() - 1;
for (int i = nums.size() - 2; i >= 0; i--) {
if (pos <= i + nums[i]) {
pos = i;
}
}
return pos == 0;
}
};

## Jump Game II - LeetCode

Jump Gameの最短ジャンプ回数を返す版。

Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.

Example:
Input: [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2.
Jump 1 step from index 0 to 1, then 3 steps to the last index.

class Solution {
public:
int jump(vector<int>& nums) {
if (nums.size() <= 1) {
return 0;
}
int pos = nums.size() - 1;
deque<int> stops = {pos};
for (int i = nums.size() - 2; i >= 0; i--) {
if (pos <= i + nums[i]) {
stops.push_back(pos);
pos = i;
while(stops.size() >= 2) {
if (stops[stops.size() - 2] > i + nums[i]) {
break;
}
stops.pop_back();
}
}
}
return stops.size();
}
};

## 区間スケジューリング問題

N個のタスクがあります。i個目のタスクは A_i日目の朝に始まり、B_i日目の夜に終わります。その間の日は全てそのタスクに専念する必要があります。
あなたはこれらのタスクを自由に選んで実行することができます。ただし、同じ日に複数のタスクを行うことはできません。実行可能なタスクの個数の最大値を求めてください。

struct Task{
int start;
int end;
bool operator<(const Task& other) {
return end < other.end;
}
bool operator<=(const Task& other) {
return end <= other.end;
}
};

int main() {
int N;
cin >> N;
vector<Task> tasks;
for(int i = 0; i < N; i++) {
int a, b;
cin >> a >> b;
tasks.push_back(Task{start: a, end: b});
}
sort(tasks.begin(), tasks.end());
int ret = 0, time = 0;
for(auto task: tasks) {
if (task.start > time) {
ret++;
time = task.end;
}
}
cout << ret << endl;
return 0;
}