Scratch Algorithms

Here are problems I worked on, and didn't really understand.

Leetcode 220

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.

You can get the N² solution with a little work and iterate through a sliding window. Getting a better solution is hard and you have to use a set. You also have to make use of upper_bound and lower_bound functions.

Here's the algorithm:

Initialize an empty set
Loop through the array, for each element x
Find the smallest element s in set that is greater than or equal to x, 
  return true if s - x <= t
Find the greatest element g in set that is smaller than or equal to x, 
  return true if x - g <= t
Put x in set
If the size of the set is larger than k, 
  remove the oldest item.
Return false

I tried getting it to work in C++ but lower_bound doesn't actually return the greatest element smaller than x.

Leetcode 139.

It's a DP problem. I solved it with my recursive chop up the string approach but it fails the time limit with a pretty small test case.

Leetcode 630.

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.

The technique here is a two stage process. First we sort by end dates. That lets us start trying to fit courses. We keep track of time and start at 0.

Then we try the next course. If you can take it, great, take it! If you can't take it, we try something special.

What we do is see if we can replace it with a course that we already took, that is longer. If we can do that, then great, take that one instead AND shift back our time by the time that we saved. SO the only thing we end up needing is a multiset of durations of courses we've taken. Then at the end we just return the size of the set!

Algrithm:

make a multiset of numbers
sort by end date
start a last_end int to 0
iterate i from 0 to end of courses
  if we can take the class : if last_end + courses[i][0] <= courses[i][1]
    take it: last_end += courses[i][0], set insert courses[i][0]
  if we CAN't take the class
    is the largest element in the taken set longer or EQUAL to this course we can't take?
      delete the largest elemetn in the set, and insert this new one. 
      last_end doesnt' stay the same! It gets shifted back by our time saved
return size of set

Code No Memo:

int maxCourse(vector<vector<int>>& courses, int last_end, int i)
{
  if(i >= courses.size()) return 0;
 
  int take = 0;
  // check if i is possible and try taking it
  if(last_end + courses[i][0] <= courses[i][1])
  {
    take = maxCourse(courses, last_end + courses[i][0], i+1) + 1;
  }
  int no_take = maxCourse(courses, last_end, i+1);
 
  return max(take, no_take);
}
 
int scheduleCourse(vector<vector<int>>& courses) {
  // sort by end
  sort(courses.begin(), courses.end(),[](vector<int>&a, vector<int>&b){return a[1]<b[1];});
 
  return maxCourse(courses, 0, 0);
}

Code With Memo

int maxCourse(vector<vector<int>>& courses, int last_end, int i,vector<vector<int>> &memo)
{
  if(i >= courses.size()) return 0;
  if(memo[last_end][i] != -1)
    return memo[last_end][i];
 
  int take = 0;
  // check if i is possible and try taking it
  if(last_end + courses[i][0] <= courses[i][1])
  {
    take = maxCourse(courses, last_end + courses[i][0], i+1, memo) + 1;
  }
  int no_take = maxCourse(courses, last_end, i+1);
 
  memo[last_end][i] = max(take, no_take);
  return memo[last_end][i];  
}
 
int scheduleCourse(vector<vector<int>>& courses) {
  // sort by end
  sort(courses.begin(), courses.end(),[](vector<int>&a, vector<int>&b){return a[1]<b[1];});
  // memo is gonna be last time and i. Need to find max time
  vector<vector<int>> memo(courses.back()[1]+1,vector<int>( courses.size()+1,-1));
 
 
  return maxCourse(courses, 0, 0,memo);
}