====== Scratch Algorithms ======

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

===== Contains Duplicates III =====

[[https://leetcode.com/problems/contains-duplicate-iii/|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:

<code>
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
</code>

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

===== Word Break =====

[[https://leetcode.com/problems/word-break/|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.

===== Course Schedule III =====

[[https://leetcode.com/problems/course-schedule-iii/solution/|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.**

{{:pasted:20200828-204101.png?500}}

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:
<code>
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>


Code No Memo:

<code cpp>
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>

Code With Memo

<code cpp>
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);
}
</code>