Grab the first timestamp, then grab all the markers until the end of the timestamp, put them in a hash list keyed by date. Now you've got a nice list of easily accessed timestamps for a time period and you also know the starting and ending point of that list of timestamps.
Next, take the start hour (i.e. strip off the minutes) of the first timestamp and assign it to an incrementing date variable you use to loop. Loop until the incrementing date variable < end date, increment the date by 15 minutes each time. At each iteration look for the date in the hash list. If you find it you are good, if you don't find it there is a problem. It should be very fast this way because of the use of a hash list. I have no idea if Perl can do a hash list as easily as OO languages though (Java, .NET etc..)