Algorithm for computing the last time a cron expression should have triggered?

I ran into this date and time constraint problem earlier this week, and haven't really found any good approach for an algorithm. Each idea I get grinds to a halt with something like what if this is a leap year? or what if this is run on the night when we change to/from DST

---

Input: A crontab expression (wikipedia on CRON format,Cron). For example:

0 */5 2,14 * * *

Meaning Every five minutes when the hour is 2 or 14

30 5 */2 1 * * */2

Meaning 5:30 past every even hour on the first of each month, every even year.

---

Output: The last time this expression was true. If run at 11:00 AM on november first, 2009, the output should be:

2009-11-01 02:55:00 

for the first example and

2008-11-01 10:05:30

for the second.

---

Some notes:

There seems to be a couple of variations of the cron expression format: Some include seconds开发者_如何学Go, some include year. The general problem should be about the same.

Feel free to apply sensible constraints; It's for example perfectly ok to don't handle years before 1970.

My current gut-feeling is that a depth-first search from year all the way down to second, backtracking when we run into invalid dates and times.

A brute-force approach could be to count backwards one day at a time, and evaluate the date part of the cron expression (there has only been about 15k days since 1970). When a valid day is found, do the same for the time part.

Answers doesn't have to contain code, I'm mostly after an algorithm outline like the ones above.

---

i don't know if you just want to get the job or you want to write the algorithm yourself for the sake of education. in the first case, probably each language has it's own implementation of cron jobs, just get that part of cron that computes the time and use it. here is a sample in java: http://blog.piotrturski.net/2013/06/testing-cron-expression.html

in case you want to write it by yourself then you should not on cron (this is the minor problem) but on TimeZone implementation. leap year is the easiest problem you will have to solve. Each timezone keeps the history of all time-related changes: administrative hour changes (daylight saving time), administrative date changes (introduction of gregorian calendar), maybe even leap seconds, and every event that impacts the time of the region represented by the timezone