如何利用分段树和二值搜索解决加权活动选择问题？

Question

给定N个作业，其中每个作业都由以下三个元素表示。

1)启动时间

2)完成时间。

( 3)利润或价值相关。

找到作业的最大利润子集，使子集中没有两个作业重叠。

我知道一个复杂度为O(N^2) (接近LIS的动态规划解)，我们只需检查以前的元素，就可以合并当前的区间，并采取合并最大的区间，直到I元素为止，.This解可以通过二进制搜索和简单排序进一步改进为O(N*log N)！

但我的朋友告诉我，它甚至可以通过使用分段树和二进制搜索解决！我不知道我将在哪里使用段树，以及如何使用。？？

你能帮上忙吗？

如有要求，对不起未作评论

我所做的是根据开始索引进行排序，通过合并以前的间隔和它们的最大可获取值，将最大可获取值存储到DPi！

 void solve()
    {
        int n,i,j,k,high;
        scanf("%d",&n);
        pair < pair < int ,int>, int > arr[n+1];// first pair represents l,r and int alone shows cost
        int dp[n+1]; 
        memset(dp,0,sizeof(dp));
        for(i=0;i<n;i++)
            scanf("%d%d%d",&arr[i].first.first,&arr[i].first.second,&arr[i].second);
        std::sort(arr,arr+n); // by default sorting on the basis of starting index
        for(i=0;i<n;i++)
        {
            high=arr[i].second;
            for(j=0;j<i;j++)//checking all previous mergable intervals //Note we will use DP[] of the mergable interval due to optimal substructure
            {
                if(arr[i].first.first>=arr[j].first.second)  
                        high=std::max(high , dp[j]+arr[i].second);
            }
            dp[i]=high;
        }
        for(i=0;i<n;i++)
                dp[n-1]=std::max(dp[n-1],dp[i]);
        printf("%d\n",dp[n-1]);
    }

int main()
{solve();return 0;}

编辑：我的工作代码最终花了我3个小时来调试它！这段代码比二进制搜索和排序要慢，这是因为一个更大的常量和糟糕的实现:P (仅供参考)

#include<stdio.h>
#include<algorithm>
#include<vector>
#include<cstring>
#include<iostream>
#include<climits>
#define lc(idx) (2*idx+1)
#define rc(idx) (2*idx+2)
#define mid(l,r) ((l+r)/2)
using namespace std;
int Tree[4*2*10000-1];
void update(int L,int R,int qe,int idx,int value)
{

    if(value>Tree[0])
        Tree[0]=value;
    while(L<R)
    {
        if(qe<= mid(L,R))
        {
            idx=lc(idx);
            R=mid(L,R);
        }
        else
        {
            idx=rc(idx);
            L=mid(L,R)+1;
        }
        if(value>Tree[idx])
            Tree[idx]=value;

    }
    return ;
}
int Get(int L,int R,int idx,int q)
{
    if(q<L )
        return 0;
    if(R<=q)
        return Tree[idx];

    return max(Get(L,mid(L,R),lc(idx),q),Get(mid(L,R)+1,R,rc(idx),q));

}
bool cmp(pair < pair < int , int > , int > A,pair < pair < int , int > , int > B)
{
    return A.first.second< B.first.second;
}
int main()
{

        int N,i;
        scanf("%d",&N);
        pair < pair < int , int  > , int > P[N];
        vector < int > V;
        for(i=0;i<N;i++)
        {
            scanf("%d%d%d",&P[i].first.first,&P[i].first.second,&P[i].second);
            V.push_back(P[i].first.first);
            V.push_back(P[i].first.second);
        }
        sort(V.begin(),V.end());
        for(i=0;i<N;i++)
        {
            int &l=P[i].first.first,&r=P[i].first.second;
            l=lower_bound(V.begin(),V.end(),l)-V.begin();
            r=lower_bound(V.begin(),V.end(),r)-V.begin();
        }
        sort(P,P+N,cmp);
        int ans=0;
        memset(Tree,0,sizeof(Tree));
        for(i=0;i<N;i++)
        {
            int aux=Get(0,2*N-1,0,P[i].first.first)+P[i].second;
            if(aux>ans)
                ans=aux;
            update(0,2*N-1,P[i].first.second,0,ans);
        }
        printf("%d\n",ans);

    return 0;
}

Answer 1

high=arr[i].second;
for(j=0;j<i;j++)//checking all previous mergable intervals //Note we will use DP[] of the mergable interval due to optimal substructure
{
    if(arr[i].first.first>=arr[j].first.second)  
    high=std::max(high, dp[j]+arr[i].second);
}
dp[i]=high;

这可以用分段树在O(log n)中完成。

首先，让我们重写一下。您所取的最大值有点复杂，因为它需要包含i和j的和的最大值。但是i在这个部分是不变的，所以让我们把它拿出来。

high=dp[0];
for(j=1;j<i;j++)//checking all previous mergable intervals //Note we will use DP[] of the mergable interval due to optimal substructure
{
    if(arr[i].first.first>=arr[j].first.second)  
    high=std::max(high, dp[j]);
}
dp[i]=high + arr[i].second;

很好，现在我们将问题简化为从满足[0, i - 1]条件的值中确定if中的最大值。

如果我们没有if，它将是段树的一个简单应用。

现在有两种选择。

O(log V) 1.处理段树的查询时间和 O(V) 内存

其中V是间隔端点的最大大小。

当您移动i时，您可以构建一个段树，将间隔开始点插入到其中。然后查询值的范围。类似这样，段树初始化为-infinity，大小为O(V)。

Update(node, index, value):
  if node.associated_interval == [index, index]:
    node.max = value
    return

  if index in node.left.associated_interval:
    Update(node.left, index, value)
  else:
    Update(node.right, index, value)

  node.max = max(node.left.max, node.right.max)

Query(node, left, right):
  if [left, right] does not intersect node.associated_interval:
    return -infinity

  if node.associated_interval included in [left, right]:
    return node.max

  return max(Query(node.left, left, right),
             Query(node.right, left, right))

[...]

high=Query(tree, 0, arr[i].first.first)
dp[i]=high + arr[i].second;
Update(tree, arr[i].first.first, dp[i])

O(log n) 2.减少段树的查询时间和 O(n) 内存

由于间隔的数量可能大大小于它们的长度，因此有理由认为我们可以以某种方式对它们进行更好的编码，因此它们的长度也是O(n)。的确，我们可以。

这涉及到对范围[1, 2*n]中的间隔进行规范化。考虑以下间隔

8 100
3 50
90 92

让我们把它们画在线上。他们看起来是这样的：

3 8 50 90 92 100

现在将它们替换为它们的索引：

1 2 3  4  5  6
3 8 50 90 92 100

然后写下你的新的时间间隔：

2 6
1 3
4 5

请注意，它们保留了初始间隔的属性:相同的间隔重叠，相同的间隔包含在彼此之间，等等。

这可以用一种方法来完成。现在可以应用相同的段树算法，除非您声明大小为2*n的段树。