r"""
    Greedy algorithm, may be exact for 1d case.
    First, choose the first item, then choose the next item that is farthest
    away from all previously chosen items. Iterate.

    CommandLine:
        python -m utool.util_alg --exec-maximin_distance_subset1d

    Notes:
        Given a set of items V.
        Let $E = V \times V$ be the the set of all item pairs.

        The goal is to return the largest subset of item such that the distance
        between any pair of items in the subset is greater than some threshold.

        Let t[u, v] be the distance between u and v.

        Let x[u, v] = 1 if the annotation pair (u, v) is included.

        Let y[u] = 1 if the annotation u is included.

        Objective:
            maximize sum(y[u] for u in V)

        subject to:
            # Annotations pairs are only included if their timedelta is less than
            # the threshold.
            x[u, v] = 0 if t[u, v] > thresh

            # If an edge is exclued at least one of its endpoints must be
            # excluded
            y[u] + y[v] - x[u, v] < 2


    Example:
        >>> # DISABLE_DOCTEST
        >>> import utool as ut
        >>> from utool.util_alg import *  # NOQA
        >>> #items = [1, 2, 3, 4, 5, 6, 7]
        >>> items = [20, 1, 1, 9, 21, 6, 22]
        >>> min_thresh = 5
        >>> K = None
        >>> result = maximin_distance_subset1d(items, K, min_thresh, verbose=True)
        >>> print(result)
        (array([1, 3, 6]), [1, 9, 22])

    Example:
        >>> # DISABLE_DOCTEST
        >>> import utool as ut
        >>> from utool.util_alg import *  # NOQA
        >>> #items = [1, 2, 3, 4, 5, 6, 7]
        >>> items = [0, 1]
        >>> min_thresh = 5
        >>> K = None
        >>> result = maximin_distance_subset1d(items, K, min_thresh, verbose=True)
        >>> print(result)

def maximin_distance_subset1d(items, K=None, min_thresh=None, verbose=False):
    r"""
    Greedy algorithm, may be exact for 1d case.
    First, choose the first item, then choose the next item that is farthest
    away from all previously chosen items. Iterate.

    CommandLine:
        python -m utool.util_alg --exec-maximin_distance_subset1d

    Notes:
        Given a set of items V.
        Let $E = V \times V$ be the the set of all item pairs.

        The goal is to return the largest subset of item such that the distance
        between any pair of items in the subset is greater than some threshold.

        Let t[u, v] be the distance between u and v.

        Let x[u, v] = 1 if the annotation pair (u, v) is included.

        Let y[u] = 1 if the annotation u is included.

        Objective:
            maximize sum(y[u] for u in V)

        subject to:
            # Annotations pairs are only included if their timedelta is less than
            # the threshold.
            x[u, v] = 0 if t[u, v] > thresh

            # If an edge is exclued at least one of its endpoints must be
            # excluded
            y[u] + y[v] - x[u, v] < 2


    Example:
        >>> # DISABLE_DOCTEST
        >>> import utool as ut
        >>> from utool.util_alg import *  # NOQA
        >>> #items = [1, 2, 3, 4, 5, 6, 7]
        >>> items = [20, 1, 1, 9, 21, 6, 22]
        >>> min_thresh = 5
        >>> K = None
        >>> result = maximin_distance_subset1d(items, K, min_thresh, verbose=True)
        >>> print(result)
        (array([1, 3, 6]), [1, 9, 22])

    Example:
        >>> # DISABLE_DOCTEST
        >>> import utool as ut
        >>> from utool.util_alg import *  # NOQA
        >>> #items = [1, 2, 3, 4, 5, 6, 7]
        >>> items = [0, 1]
        >>> min_thresh = 5
        >>> K = None
        >>> result = maximin_distance_subset1d(items, K, min_thresh, verbose=True)
        >>> print(result)
    """
    if False:
        import pulp
        # Formulate integer program
        prob = pulp.LpProblem("MaxSizeLargeDistSubset", pulp.LpMaximize)
        # Solution variable indicates if set it chosen or not
        item_indices = list(range(len(items)))
        pair_indices = list(ut.combinations(item_indices, 2))
        x = pulp.LpVariable.dicts(name='x', indexs=pair_indices,
                                  lowBound=0, upBound=1, cat=pulp.LpInteger)
        y = pulp.LpVariable.dicts(name='y', indexs=item_indices,
                                  lowBound=0, upBound=1, cat=pulp.LpInteger)
        # minimize the number of sets
        prob.objective = sum(y[i] for i in item_indices)

        # subject to
        count = 0
        for u, v in pair_indices:
            # Minimum thresh constraint
            if abs(items[u] - items[v]) < min_thresh:
                prob.add(x[(u, v)] == 0, name='thresh_%r' % (count,))
                count += 1

        count = 0
        for u, v in pair_indices:
            prob.add(y[u] + y[v] - x[(u, v)] <= 1, 'exclusion_%r' % (count,))
            count += 1

        pulp.PULP_CBC_CMD().solve(prob)
        # Read solution
        flags = [y[i].varValue >= 1.0 for i in item_indices]
        chosen_items_idxs = ut.where(flags)
        chosen_items = ut.take(items, chosen_items_idxs)

        # total_value = sum([val for val, flag in zip(values, flags) if flag])
        # items_subset = [item for item, flag in zip(items, flags) if flag]
        # each element is covered
        # containing_sets = [i for i in set_indices if e in candidate_sets_dict[i]]
        # prob.add(sum(x[i] for i in containing_sets) >= 1)

    import utool as ut
    import vtool as vt
    points = np.array(items)[:, None]
    # Initial sorting of 1d points
    initial_sortx = points.argsort(axis=0).flatten()
    points = points.take(initial_sortx, axis=0)

    if K is None:
        K = len(items)

    def distfunc(x, y):
        return np.abs(x - y)

    assert points.shape[1] == 1
    assert len(points) >= K, 'cannot return subset'
    if K == 1:
        current_idx = [0]
    else:
        current_idx = [0, -1]
        if min_thresh is not None and distfunc(points[0], points[-1])[0] < min_thresh:
            current_idx = [0]
    chosen_mask = vt.index_to_boolmask(current_idx, len(points))

    for k in range(2, K):
        unchosen_idx = np.nonzero(~chosen_mask)[0]
        unchosen_items = points.compress(~chosen_mask, axis=0)
        chosen_items = points.compress(chosen_mask, axis=0)
        distances = distfunc(unchosen_items, chosen_items.T)
        min_distances = distances.min(axis=1)
        argx = min_distances.argmax()
        if min_thresh is not None:
            if min_distances[argx] < min_thresh:
                break
        new_idx = unchosen_idx[argx]
        chosen_mask[new_idx] = True

    # Put chosen mask back in the input order of items
    chosen_items_mask = chosen_mask.take(initial_sortx.argsort())
    chosen_items_idxs = np.nonzero(chosen_items_mask)[0]
    chosen_items = ut.take(items, chosen_items_idxs)
    #current_idx = np.nonzero(chosen_mask)[0]
    if verbose:
        print('Chose subset')
        chosen_points = points.compress(chosen_mask, axis=0)
        distances = (spdist.pdist(chosen_points, distfunc))
        print('chosen_items_idxs = %r' % (chosen_items_idxs,))
        print('chosen_items = %r' % (chosen_items,))
        print('distances = %r' % (distances,))
    return chosen_items_idxs, chosen_items