5. 贪心算法

5. 贪心算法

示例场景：活动选择问题，选择尽可能多的不重叠活动。

import React, { useState } from "react";

function selectActivities(activities) {
  activities.sort((a, b) => a.end - b.end);

  const selectedActivities = [activities[0]];
  let lastSelected = activities[0];

  for (let i = 1; i < activities.length; i++) {
    if (activities[i].start >= lastSelected.end) {
      selectedActivities.push(activities[i]);
      lastSelected = activities[i];
    }
  }

  return selectedActivities;
}

function ActivitySelector() {
  const [activities, setActivities] = useState([
    { start: 1, end: 3 },
    { start: 2, end: 5 },
    { start: 3, end: 9 },
    { start: 5, end: 8 },
    { start: 8, end: 10 },
  ]);
  const [selectedActivities, setSelectedActivities] = useState([]);

  const select = () => {
    const selected = selectActivities(activities);
    setSelectedActivities(selected);
  };

  return (
    <div>
      <h2>活动选择问题</h2>
      <button onClick={select}>选择活动</button>
      <h3>所有活动</h3>
      <ul>
        {activities.map((activity, index) => (
          <li key={index}>
            {`活动 ${index + 1}: 开始时间 ${activity.start}, 结束时间 ${
              activity.end
            }`}
          </li>
        ))}
      </ul>
      <h3>选中的活动</h3>
      <ul>
        {selectedActivities.map((activity, index) => (
          <li key={index}>
            {`活动 ${index + 1}: 开始时间 ${activity.start}, 结束时间 ${
              activity.end
            }`}
          </li>
        ))}
      </ul>
    </div>
  );
}

function App() {
  return (
    <div>
      <h1>贪心算法</h1>
      <ActivitySelector />
    </div>
  );
}

export default App;

在处理复杂数据结构和优化性能时。