To be honest, I think you'll be fine. £36,000 is a pretty high salary for the UK (the average individual salary in Scotland is £21,000) and a relatively normal rental amount (average rent in Scotland is about £540 per month).
I earn just under £24,000 base salary (plus shift allowance of about £5,000) and I pay £550 per month in rent (1-bed flat). I'm single, but even with bills, food and running my car I can still put anywhere between £500 and £1,000 into my savings each month towards other expenses (clothes, household goods etc.), holidays and a house deposit - just depends how much I've spent on other things (like trips, clothes, the gym, going out etc.)
In comparison, I have a friend who earns around £14,000 per year and pays over £700 in rent each month (it's much more expensive where she lives)... and she's living pretty much paycheque to paycheque, though she does just about manage it (she usually manages a week-long holiday somewhere in Europe each year).