Каким образом здесь утроена структура бд?
Произвольным. Здесь, похоже, вы видите результат какой-то выборки.
Какой тип имеют поля address, company?
String. А данные - либо array, либо stdClass, смотря как делали json_decode().
Как мне их записать в бд
Получить id нужных пользователей, затем сделать один insert для создания задачи и еще один insert для связывания задачи с пользователями.
Но при чем тут задачи и пользователи, если разговор идет про адреса и компании?
получать их в таком виде
Один запрос на задачу и один запрос на ее пользователей. На php сформировать массив в нужном формате.
Технически, запрос можно сделать один на все данные, но данные будут избыточны.