Arrowstreet Capital hackerrank

一共8题，其中3题选择，剩下的题包括shortest substring containing all chars，还有几道比较简单的记不起来了，印象比较深的是最后一道我没写出来，题目放这里了大家帮我想想该怎么做

input two array arrival and departure，arrival[i] and departure[i] are i th person's arrival date and departure date respectively. Each day you can only meet one person. Find the max number of purple you can meet before they leave.

EX: arrival = {1,2,2,3}, departure = {2,2,3,4}, then return 4 because you can meet person0 on day1, person1 on day2, person2 on day3, person3 on day4. However, if arrival = {2,2,2,3}, departure = {2,3,4,4} then return 3.

之前乍一看以为是经典的interval scheduling problem用greedy select earliest end time的，但这道题不一样那么做是不对的，想问问大家有什么想法吗？

我搞了一个解法感觉是对的： sort by earliest start time, if tie then sort by earliest end time. 然后时间轴从左到右过一遍，优先把时间点分配给前面的interval.
BTW, 楼主面的是software engineer还是quantitative developer呀

dfs 就好了
def f(arrival, departure):
    visited = set()
    f.res = 0
    def dfs(idx, path):
        f.res = max(f.res, path)
        for i in range(idx, len(arrival)):
            for j in range(arrival[i], departure[i] + 1):
                if not j in visited:
                    visited.add(j)
                    dfs(idx + 1, path + 1)
                    visited.remove(j)
    dfs(0, 0)
    return f.res

print(f([2,2,2,3], [2,3,4,4]))

请问楼主有后续了吗？感谢～

小熊牛牛 发表于 2019-12-4 08:45
dfs 就好了
def f(arrival, departure):
    visited = set()

如果arrival = [1,2,2,3], departure = [4,2,2,5] 答案好像就不太对了

Greedy吧？