For an optimal selection, one possible sequencing is always the one respecting the order of arrival time $S_0$. Another may be possible, but you can check that you always can do the switches to obtain $S_0$. This is due to the fact that all jobs have the same $d$.
Thus, your problem is equivalent to select the subset of jobs which do not overlap if they are executed as soon as possible in arrival time order.
Then you can do an approximative greedy algorithm considering jobs in increasing duration order. Counting the duration sorting, this has a $O(N \log(N))$ time complexity. It would generally give a very good result but might fail for example on $(a[i], t[i]) = [(0, 60), (30, 50), (60, 60)]$ with $d = 60$.
Or you can do a dynamic programming on $T$ array of $t(n)$, the soonest time at which $n$ jobs are achieved.
Initially, $T_0 = [0, +\infty, +\infty ..., +\infty]$, it has size $N+1$, the number of jobs (+ 0 index). The jobs are considered in increasing arrival time order. $T_k$ is the state of $T$ after considering $k^{th}$ job.
To keep track of the selection, you need an array $previous$ of size $N \times N$ and an array $lastElement$ of size $N$. All are initially filled with -1. $lastElements[i]$ tracks the index of the last added job for $T_{i+1}$. $previous[i][j]$ tracks the element added just before j for $T_{i+1}$.
Then the sub-problem is to compute $T_{k+1}$ from $T_{k}$.
This is the pseudo-code:
function next_job(T_last, a_k, t_k, d):
T = T_last
for i from 0 to N-1 do:
if T_last[i] == +inf then break
begin = max(a_k, T_last[i])
end = begin + t_k
if (end > a_k + d) then continue
if (T[i+1] < end) then:
T[i+1] = min(T[i+1], end)
lastElement[i] = k
if(i > 1) previous[i, k] = lastElement[i-1]
end
end
return T
The final result is of course the largest $i$ such that $T[i]$ is not $+\infty$.
It has a $O(N^2)$ overall time complexity.
To obtain the selection, you pick $elem0 = lastElement[i-1]$, then $elem1 = previous[i-1, elem0]$, then $elem2 = previous[i-2, elem1]$ and so on until you have your i elements.
Let's make a small example with $(a[i], t[i]) = [(0, 60), (10, 30), (50, 20)]$, $d=60$ :
- $T_0 = [0, +\infty, +\infty, +\infty]$ => initialization
- $T_1 = [0, 60, +\infty, +\infty]$ => one job may be achieved at time=60
- $T_2 = [0, 40, +\infty, +\infty]$ => up to now only one job may be selected, but job (10, 30) took the place of (0, 60) as it can be achieved sooner.
- $T_3 = [0, 40, 70, +\infty]$ => optimal solution selects 2 jobs.
At the end, $lastElements = [1, 2, -1]$ (starting job indexing at 0)
and $previous = [[-1, -1, -1] [-1, -1, 1] [-1, -1, -1]]$. This let you track the optimal selection $\{1, 2\}$.