I would say your query should be based on the junction object.
Therefore you don't need a map, because a junction object itself has the Map characteristic (key => value)
List<Account> accountsToUpdate = new List<Account>();
for (AccountAdress addr : [SELECT id, startdate, enddate, account__c, addres__c
Your first Approach does not contain the startDate so it does not match your criteria. Anyway the second approach seems preferable. Since it seems a periodic task (dialy?) I would use a Scheduleable Job to run it earch day after midnight...