Just explaining how this works: In order to quit a job, you give notice. There will be some minimum notice period due to your contract and your country’s laws. If you have at least the required notice, the company has to accept that notice.
What can the company do? If you gave notice more than the legally required, they could give you a shorter notice. So if you gave three months notice, and only one month is required, they could give you one month notice. That would be nasty, but possible. Fortunately that didn’t happen.
The normal thing is that you work and get paid to the end of the notice period. But sometimes companies don’t want you in their office anymore, often if you are in a position where you could cause damage. The company can do one of two thing:
First, they can send you on gardening leave. Which means you stay at home, you don’t work, you still get paid, you are still employed. You have time to renovate your home, look after your garden, meet the kids. You can NOT start another job, because you are still employed.
Second, they can give you “payment in lieu of notice”. That means, instead of having to employ you, they can lay you off, but they need to pay your salary for the notice period. That's what happened to you if your description is correct. This may have tax advantages for the company, but for you it’s mostly the same. Important is that although you are technically unemployed, no sane employer would treat you as unemployed. (That doesn’t mean your new employer might not be one of the insane ones).
What I would tell you is to go to the new employer and tell them “my old employer is giving me payment in lieu of notice, so i can start two months earlier”. You can do them a favour if they want it.
And what do you mean “How do I justify this to my next employer?” There is nothing to justify. You are getting paid all the time. Even better, if they let you start earlier, you get paid twice for a month or two! If you say “I gave three months notice, but I got paid in lieu of notice”, that is a complete and totally acceptable statement of what happened.