Функциональное программирование (в частности, SML) список интервальных вопросов - PullRequest
Новая
       9

Функциональное программирование (в частности, SML) список интервальных вопросов

0 голосов
/ 01 октября 2018

У меня проблема с тем, что при наличии двух списков, представляющих расписания (периоды, когда кто-то занят), я хочу вернуть доступное время, когда оба человека / списки доступны.Например, 

create_schedule([(1,2), (4,6), (8, 12)], [(1,3), (5,9)]] => [(0, 1), (3,4)]

Все времена начинаются с 0 и доходят до максимального числа, указанного во входных данных.Это мой подход:

  1. Используйте функцию List.concat, чтобы сгладить список.Таким образом, ввод становится [(1,2), (4,6), (8, 12), (1,3), (5,9)].
  2. Сортировка по первому элементу в каждом кортеже => [(1,2), (1,3), (4, 6), (5,9), (8,12)].
  3. Объедините интервалы, чтобы получилось [(1,3), (4, 12)].
  4. Возьмите числа между каждым кортежем.Для этого конкретного примера мне нужно вставить кортеж (0,0) в начале.Так что для [(0,0), (1,3), (4,12)] средние значения равны (0, 1) и (3,4), и это ответ.

Я не могу использовать рекурсию, и мое решение должно быть в O (nlogn).Я уже кодировал функцию слияния и сортировки.Теперь мне нужно создать функцию, которая принимает средние значения, поэтому [(0,0), (1,3), (4,12)] становится [(0, 1), (3,4)] (ответ).Я не уверен, как это сделать без рекурсии.Я должен использовать функции более высокого порядка, такие как map, foldl, foldr, filter и т. Д. Я чувствую, что у меня хорошее начало, но у меня много проблем с его завершением.Любые советы будут очень полезны!

1 Ответ

0 голосов
/ 01 октября 2018

Мне нужно создать функцию, которая принимает средние значения, так что [(0,0), (1,3), (4,12)] становится [(0, 1), (3,4)] (ответ).

Один подход: начиная с [(0,0), (1,3), (4,12)], вы можетеиспользуйте <a href="http://sml-family.org/Basis/list.html" rel="nofollow noreferrer">List</a>.tl и <a href="http://sml-family.org/Basis/list-pair.html" rel="nofollow noreferrer">ListPair</a>.zip, чтобы получить [((0,0),(1,3)), ((1,3),(4,12))].Тогда вам просто нужна функция, которая принимает ((0,0),(1,3)) до (0,1) и ((1,3),(4,12)) до (3,4).

Другой подход: вместо вставки (0,0) в начале списка, вы можете использовать (0, nil) как значение <em>init</em> при вызове <a href="http://sml-family.org/Basis/list.html" rel="nofollow noreferrer">List</a>.foldl.<em>f</em> будет иметь тип (int * int) * (int * int list) и займет ((1,3),(0,nil)) до (3,[(0,1)]) и ((4,12),(3,[(0,1)])) до (12,[(3,4),(0,1)]).Вы получите (12,[(3,4),(0,1)]), откуда вы можете легко получить [(0,1),(3,4)].

...