You can make yourself a "tiny millis timestamp" that can handle overflow just like its 'unsigned long' brother. Example:
unsigned int littleNow = millis()
subsequently, you can safely do things like:
unsigned int lastLittleNow;
...
if (littleNow - lastLittleNow >= interval) { ...
with the restriction than 'interval' can be no longer than 65535ms