Greedy Approach¶

/*
Question:
Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie.

Each child i has a greed factor g[i], which is the minimum size of a cookie that the child will be content with; and each cookie j has a size s[j]. If s[j] >= g[i], we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number.

Example:
Input: g = [1,2,3], s = [1,1]
Output: 1
Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3. 
And even though you have 2 cookies, since their size is both 1, you could only make the child whose greed factor is 1 content.
You need to output 1.

Approach:
1. Sort the greed factor array g and the cookie size array s in ascending order.
2. Initialize a counter variable child to track the number of content children.
3. Iterate over the cookie size array s and check if the current cookie size is greater than or equal to the greed factor of the current child.
4. If it is, increment the child counter and move to the next child.
5. Finally, return the total number of content children.

Complexity Analysis:
- Sorting the arrays takes O(n log n) time, where n is the size of the arrays.
- The iteration over the arrays takes O(n) time.
- Therefore, the overall time complexity is O(n log n).

Code:
*/

int findContentChildren(vector<int>& g, vector<int>& s) {
    sort(g.begin(), g.end());
    sort(s.begin(), s.end());
    int child = 0;
    for (int i = 0; i < s.size() && child < g.size(); i++) {
        if (s[i] >= g[child])
            child++;
    }
    return child;
}

/*
Question:
Given weights and values of N items, we need to put these items in a knapsack of capacity W to get the maximum total value in the knapsack.
Note: Unlike 0/1 knapsack, you are allowed to break the item.

Example:
Input:
N = 3, W = 50
values[] = {60, 100, 120}
weight[] = {10, 20, 30}
Output:
240.00
Explanation: Total maximum value of items
we can have is 240.00 from the given
capacity of the sack.

Approach:
1. We will define a comparator function that compares items based on their value/weight ratio in descending order.
2. We will sort the items array based on the comparator function.
3. Initialize a variable loot to keep track of the total value in the knapsack.
4. Iterate over the items array, starting from the item with the highest value/weight ratio.
5. If the weight of the current item is greater than the remaining capacity W, we take a fraction of the item to fill the remaining capacity.
   The fraction is determined by the remaining capacity divided by the weight of the current item.
6. Add the fraction of the item's value to the loot.
7. Reduce the remaining capacity by the weight of the item.
8. Repeat steps 5-7 until the remaining capacity becomes zero or all items are considered.
9. Finally, return the loot, which represents the maximum total value in the knapsack.

Complexity Analysis:
- The sorting step takes O(n log n) time, where n is the number of items.
- The iteration over the items takes O(n) time.
- Therefore, the overall time complexity is O(n log n).

Code:
*/

static bool comp(Item a, Item b) {
    return a.value / (a.weight * 1.0) > b.value / (b.weight * 1.0);
}

double fractionalKnapsack(int W, Item arr[], int n) {
    sort(arr, arr + n, comp);
    double loot = 0;
    for (int i = 0; i < n && W; i++) {
        if (arr[i].weight > W) {
            loot += (W * (arr[i].value / (arr[i].weight * 1.0)));
            W = 0;
        } else {
            loot += arr[i].value;
            W -= arr[i].weight;
        }
    }
    return loot;
}

/*
Question:
At a lemonade stand, each lemonade costs $5. Customers are standing in a queue to buy from you and order one at a time (in the order specified by bills).
Each customer will only buy one lemonade and pay with either a $5, $10, or $20 bill. You must provide the correct change to each customer so that the net transaction is that the customer pays $5.
Note that you do not have any change in hand at first.
Given an integer array bills where bills[i] is the bill the ith customer pays, return true if you can provide every customer with the correct change, or false otherwise.

Example:
Input: bills = [5, 5, 5, 10, 20]
Output: true
Explanation:
From the first 3 customers, we collect three $5 bills in order.
From the fourth customer, we collect a $10 bill and give back a $5.
From the fifth customer, we give a $10 bill and a $5 bill.
Since all customers got correct change, we output true.

Approach:
- We maintain two counters: `fiveCnt` to count the number of $5 bills and `tenCnt` to count the number of $10 bills we have.
- We iterate over the bills array.
- For each bill, we check if it is $5, $10, or $20.
  - If it is $5, we increment the `fiveCnt`.
  - If it is $10, we increment the `tenCnt` and decrement the `fiveCnt` since we need to give back a $5 bill as change.
  - If it is $20, we try to give back a $10 bill and a $5 bill as change if we have them. Otherwise, we try to give back three $5 bills.
- After each transaction, we check if the `fiveCnt` is negative, which means we have given a $5 bill that we actually don't have. In this case, we return false.
- If we successfully process all the bills without any negative `fiveCnt`, we return true.

Complexity Analysis:
- The time complexity of this approach is O(N), where N is the length of the bills array.
- We iterate over the bills array once to process each bill.
- The space complexity is O(1) as we are using only a constant amount of extra space.

Code:
*/

bool lemonadeChange(vector<int>& bills) {
    int fiveCnt = 0, tenCnt = 0;
    for (auto bill : bills) {
        if (bill == 5)
            fiveCnt++;
        else if (bill == 10) {
            tenCnt++;
            fiveCnt--;
        } else {
            if (tenCnt) {
                tenCnt--;
                fiveCnt--;
            } else
                fiveCnt -= 3;
        }
        // this means we have given $5 which we actually don't have
        if (fiveCnt < 0)
            return false;
    }
    return true;
}

/*
Question:
Given a string s containing only three types of characters: '(', ')' and '*', return true if s is valid.
The following rules define a valid string:
- Any left parenthesis '(' must have a corresponding right parenthesis ')'.
- Any right parenthesis ')' must have a corresponding left parenthesis '('.
- Left parenthesis '(' must go before the corresponding right parenthesis ')'.
- '*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string "".

Example:
Input: s = "(*))"
Output: true

Approach:
- We maintain two counters `cmin` and `cmax` to keep track of the minimum and maximum possible number of open parentheses.
- We iterate over the characters in the string.
- For each character:
  - If it is '(', we increment both `cmin` and `cmax`.
  - If it is ')', we decrement `cmax` and update `cmin` to the maximum of `cmin - 1` and 0 (to handle cases where '*' is treated as '(').
  - If it is '*', we increment `cmax` (considering '*' as '(') and update `cmin` to the maximum of `cmin - 1` and 0 (to handle cases where '*' is treated as ')').
  - If `cmax` becomes negative at any point, it means even after treating all '*' as '(' we can't maintain balance, so we return false.
- Finally, we check if `cmin` is 0, which means we have balanced parentheses.

Complexity Analysis:
- The time complexity of this approach is O(N), where N is the length of the string s.
- We iterate over each character once.
- The space complexity is O(1) as we are using only a constant amount of extra space.

Code:
*/

// NOTE- this approach is not intuitive but the most optimal however we can use recursion to solve this problem and optimize it using dp.
// We can also solve this using recursion where in the case of '*' we will make 3 recursion calls,
//  1-> where opencnt++,
//  2-> where opencnt
//  3-> where opencnt--
//  The base case would be at end if opencnt == 0 return true else false.

bool checkValidString(string s) {
    int cmin = 0, cmax = 0;
    for (auto c : s) {
        if (c == '(') {
            cmax++;
            cmin++;
        } else if (c == ')') {
            cmax--;
            cmin = max(cmin - 1, 0);
        } else { // this is the case of '*'
            cmax++; // if we treat '*' as '('
            cmin = max(cmin - 1, 0); // if we treat '*' as ')'
        }
        if (cmax < 0) // this means even after treating all '*' as '(' we can't maintain balance
            return false;
    }
    return (cmin == 0);
}

/*
Question:
There is one meeting room in a firm. There are N meetings in the form of (start[i], end[i]) where start[i] is the start time of meeting i and end[i] is the finish time of meeting i.
What is the maximum number of meetings that can be accommodated in the meeting room when only one meeting can be held in the meeting room at a particular time?
Note: Start time of one chosen meeting can't be equal to the end time of the other chosen meeting.

Example:
Input:
N = 6
start[] = {1,3,0,5,8,5}
end[] = {2,4,6,7,9,9}
Output: 4
Explanation: Maximum four meetings can be held with the given start and end timings.
The meetings are - (1, 2), (3, 4), (5, 7), and (8, 9)

Approach:
- We store the meetings as pairs of (end[i], start[i]) in a vector.
- We sort the vector in non-decreasing order based on the end time of meetings.
- We initialize the answer as 1 and the previous meeting end time as the end time of the first meeting in the sorted vector.
- We iterate over the meetings starting from the second meeting.
  - If the start time of the current meeting is greater than the previous meeting end time, we increment the answer and update the previous meeting end time.
- Finally, we return the answer.

Complexity Analysis:
- The time complexity of this approach is O(NlogN), where N is the number of meetings.
- Sorting the meetings based on the end time takes O(NlogN) time.
- The space complexity is O(N) as we store the meetings in a vector.

Code:
*/

int maxMeetings(int start[], int end[], int n)
{
    vector<pair<int, int>> meet;
    for (int i = 0; i < n; i++) {
        meet.push_back({end[i], start[i]});
    }
    sort(meet.begin(), meet.end());
    int ans = 1, prev = meet[0].first;
    for (int i = 1; i < n; i++) {
        if (meet[i].second > prev) {
            ans++;
            prev = meet[i].first;
        }
    }
    return ans;
}

/*
Question:
You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.
Return true if you can reach the last index, or false otherwise.

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

Approach:
- We maintain a variable 'farthest' to keep track of the farthest position we can reach.
- We iterate over the array from left to right.
- At each position, we check if the current position is reachable from the previous farthest position.
- If the current position is beyond the farthest position, it means we cannot reach the end, so we return false.
- Otherwise, we update the farthest position by taking the maximum of the current farthest and the current position plus the maximum jump length at that position.
- Finally, if we reach the end of the array or beyond it, we return true.

Complexity Analysis:
- The time complexity of this approach is O(N), where N is the length of the array nums.
- We iterate over the array once to update the farthest position.
- The space complexity is O(1) as we use only a constant amount of extra space.

Code:
*/

bool canJump(vector<int>& nums) {
    int farthest = 0;
    for (int i = 0; i < nums.size(); i++) {
        if (farthest < i)
            return false;
        farthest = max(farthest, nums[i] + i);
    }
    return true;
}

/*
Question:
You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].
Each element nums[i] represents the maximum length of a forward jump from index i.
Return the minimum number of jumps to reach nums[n - 1].

Example:
Input: nums = [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.

Approach:
- We maintain three variables: 'steps', 'end', and 'farthest'.
- 'steps' keeps track of the minimum number of jumps required.
- 'end' represents the current farthest position that we can reach.
- 'farthest' stores the farthest position we can reach by taking a jump from the current position.
- We iterate over the array from left to right, except for the last element.
- At each position, we update the 'farthest' by taking the maximum of the current farthest and the current position plus the maximum jump length at that position.
- If the 'farthest' position is greater than or equal to the last index, it means we can reach the end, so we return 'steps + 1'.
- When we reach the 'end' position, it means we have taken the maximum number of jumps from the previous step.
- So, we increment 'steps' by 1 and update the 'end' to the 'farthest' position.
- Finally, we return the 'steps' as the minimum number of jumps required.

Complexity Analysis:
- The time complexity of this approach is O(N), where N is the length of the input array 'nums'.
- We iterate over the array once.
- The space complexity is O(1) as we use only a constant amount of extra space.

Code:
*/

int jump(vector<int>& nums) {
    int steps = 0, end = 0, farthest = 0;
    for (int i = 0; i < nums.size() - 1; i++) {
        farthest = max(farthest, nums[i] + i);
        if (farthest >= nums.size() - 1)
            return steps + 1;
        if (i == end) {
            steps++;
            end = farthest;
        }
    }
    return steps;
}

/*
Question:
Given arrival and departure times of all trains that reach a railway station, find the minimum number of platforms required for the railway station so that no train is kept waiting.
Consider that all the trains arrive on the same day and leave on the same day. Arrival and departure time can never be the same for a train, but we can have the arrival time of one train equal to the departure time of another. At any given instance of time, the same platform cannot be used for both the departure of a train and the arrival of another train. In such cases, we need different platforms.

Example:
Input: n = 6
arr[] = {0900, 0940, 0950, 1100, 1500, 1800}
dep[] = {0910, 1200, 1120, 1130, 1900, 2000}
Output: 3
Explanation:
Minimum 3 platforms are required to safely arrive and depart all trains.

Approach:
- We sort the arrival and departure arrays in non-decreasing order.
- We initialize variables 'i', 'j', 'plat', and 'ans' to 0.
- We iterate over the arrival array using 'i' and departure array using 'j'.
- If the arrival time at index 'i' is less than or equal to the departure time at index 'j', it means a train is arriving and we need an additional platform.
  - So, we increment 'i' and 'plat'.
  - We update 'ans' with the maximum value of 'ans' and 'plat'.
- If the arrival time is greater than the departure time, it means a train has departed and we can free up a platform.
  - So, we increment 'j' and decrement 'plat'.
- Finally, we return 'ans' as the minimum number of platforms required.

Complexity Analysis:
- The time complexity of this approach is O(NlogN), where N is the number of trains.
- We sort the arrival and departure arrays, which takes O(NlogN) time.
- The space complexity is O(1) as we use only a constant amount of extra space.

Code:
*/

int findPlatform(int arr[], int dep[], int n)
{
    sort(arr, arr + n);
    sort(dep, dep + n);
    int i = 0, j = 0, plat = 0, ans = 0;
    while (i < n) {
        if (arr[i] <= dep[j]) {
            i++;
            plat++;
            ans = max(ans, plat);
        }
        else {
            j++;
            plat--;
        }
    }
    return ans;
}

/*
Question:
Given a set of N jobs where each job 'i' has a deadline and profit associated with it. Each job takes 1 unit of time to complete, and only one job can be scheduled at a time. We earn the profit associated with a job if and only if the job is completed by its deadline. Find the number of jobs done and the maximum profit.

Example:
Input:
N = 4
Jobs = {(1,4,20),(2,1,10),(3,1,40),(4,1,30)}
Output:
2 60
Explanation:
Job1 and Job3 can be done with a maximum profit of 60 (20+40).

Approach:
- We create a vector of pairs 'jobs' to store the profit and deadline of each job.
- We sort the 'jobs' vector in non-increasing order of profits.
- We initialize a vector 'deadline' of size 'n+1' and set all elements to -1.
- We also initialize variables 'ans' and 'cnt' to 0.
- We iterate over the 'jobs' vector.
  - For each job, we get the deadline and profit.
  - We check from the deadline to 1 (in reverse order) if there is any slot available to schedule the job.
  - If we find an available slot, we mark it as scheduled by setting 'deadline[dead]' to 1, increment 'cnt' and add the profit to 'ans'.
- Finally, we return a vector containing 'cnt' and 'ans' as the number of jobs done and the maximum profit.

Complexity Analysis:
- The time complexity of this approach is O(NlogN), where N is the number of jobs.
- This is due to the sorting operation on the 'jobs' vector based on profits.
- The space complexity is O(N) as we use additional vectors to store the jobs and deadlines.

Code:
*/

static bool comp(pair<int,int> a, pair<int,int> b) {
    return a.first > b.first;
}

vector<int> JobScheduling(Job arr[], int n) {
    vector<pair<int,int>> jobs;
    for(int i = 0; i < n; i++) {
        jobs.push_back({arr[i].profit, arr[i].dead});
    }
    sort(jobs.begin(), jobs.end(), comp);
    vector<int> deadline(n+1, -1);
    int ans = 0, cnt = 0;
    for(int i = 0; i < n; i++) {
        int dead = jobs[i].second;
        int profit = jobs[i].first;
        while(dead >= 1 && deadline[dead] != -1) {
            dead--;
        }
        if(dead >= 1) {
            deadline[dead] = 1;
            cnt++;
            ans += profit;
        }
    }
    return {cnt, ans};
}

/*
Question:
There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.
You are giving candies to these children subjected to the following requirements:
- Each child must have at least one candy.
- Children with a higher rating get more candies than their neighbors.
Return the minimum number of candies you need to have to distribute the candies to the children.

Example:
Input: ratings = [1,0,2]
Output: 5
Explanation: You can allocate to the first, second, and third child with 2, 1, 2 candies respectively.

Approach:
- We start by assigning 1 candy to each child as the minimum requirement.
- Then, we iterate from left to right and check if the current child has a higher rating than the previous child.
- If yes, we increment the number of candies for the current child by 1 compared to the previous child.
- Next, we iterate from right to left and check if the current child has a higher rating than the next child.
- If yes, we take the maximum of the current child's candies and the next child's candies plus 1.
- Finally, we sum up all the candies assigned to get the minimum number of candies required.

Complexity Analysis:
- The time complexity of this approach is O(N), where N is the number of children.
- We iterate over the ratings twice to assign the candies.
- The space complexity is O(N) as we use an additional vector to store the number of candies assigned to each child.

Code:
*/

int candy(vector<int>& ratings) {
    int n = ratings.size();
    if(n == 1) return 1;
    vector<int> num(n, 1);
    for(int i = 1; i < n; i++) {
        if(ratings[i] > ratings[i-1]) {
            num[i] = num[i-1] + 1;
        }
    }
    for(int i = n-2; i >= 0; i--) {
        if(ratings[i] > ratings[i+1]) {
            num[i] = max(num[i], num[i+1] + 1);
        }
    }
    int sum = 0;
    for(auto it : num) {
        sum += it;
    }
    return sum;
}

/*
Question:
You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and the end of the ith interval and intervals is sorted in ascending order by starti. You are also given an interval newInterval = [start, end] that represents the start and end of another interval.

Insert newInterval into intervals such that intervals is still sorted in ascending order by starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).

Return intervals after the insertion.

Example:
Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

Approach:
- We iterate through the intervals and compare them with the newInterval.
- There are three possible cases:
  1. The newInterval is before the current interval: We add the newInterval and update the newInterval to the current interval.
  2. The newInterval is after the current interval: We add the current interval to the result.
  3. The newInterval overlaps with the current interval: We update the newInterval to cover the merged interval.

Complexity Analysis:
- The time complexity of this approach is O(N), where N is the number of intervals.
- We iterate through the intervals once.
- The space complexity is O(1) as we are using a constant amount of additional space.

Code:
*/

vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
    vector<vector<int>> ans;
    int n = intervals.size();

    for(int i = 0; i < n; i++) {
        // newInterval is after the current interval
        if(intervals[i][1] < newInterval[0]) {
            ans.push_back(intervals[i]);
        }
        // newInterval is before the current interval
        else if(newInterval[1] < intervals[i][0]) {
            ans.push_back(newInterval);
            newInterval = intervals[i];
        }
        // newInterval overlaps with the current interval
        else {
            newInterval[0] = min(intervals[i][0], newInterval[0]);
            newInterval[1] = max(intervals[i][1], newInterval[1]);
        }
    }
    ans.push_back(newInterval);
    return ans;
}

/*
Question:
Given an array of intervals intervals where intervals[i] = [starti, endi], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Example:
Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping.

Approach:
- We sort the intervals based on the end time in ascending order.
- We initialize a count variable to keep track of the number of intervals that need to be removed.
- We initialize the end variable to store the end time of the first interval.
- Then, we iterate through the intervals starting from the second interval.
- If the start time of the current interval is less than the end time of the previous interval, it means there is an overlap.
- In that case, we increment the count variable since we need to remove this interval to make the rest non-overlapping.
- Otherwise, if there is no overlap, we update the end variable to the end time of the current interval.
- Finally, we return the count variable, which represents the minimum number of intervals to remove.

Complexity Analysis:
- The time complexity of this approach is O(NlogN), where N is the number of intervals.
- Sorting the intervals takes O(NlogN) time, and iterating through the intervals takes O(N) time.
- The space complexity is O(1) as we are not using any additional data structures.

Code:
*/

bool comp(vector<int>& a, vector<int>& b) {
    return a[1] < b[1];
}

int eraseOverlapIntervals(vector<vector<int>>& intervals) {
    if(intervals.size() < 2) return 0;
    sort(intervals.begin(), intervals.end(), comp);
    int cnt = 0, end = intervals[0][1];
    for(int i = 1; i < intervals.size(); i++) {
        if(intervals[i][0] < end) {
            cnt++;
        }
        else {
            end = intervals[i][1];
        }
    }
    return cnt;
}