Hi
Yes it could be an option but using Earliest you are not able to trigger on Status "Waiting for host" only.
That means if the job is currently running and exceeds max runtime it will be chancelled as well.
Plan B would be using an agent group for your job.
Another possibility would be checking in Prescript of your JOBS, if the Agent is up and running using SYS_HOST_ALIVE
if not, you can read an alternative agent from a VARA or out of an agent group.
cheers, Wolfgang