Greedy Algorithms

public class ActivitySelection
{
    public class Activity
    {
        public string Name { get; set; }
        public int Start { get; set; }
        public int End { get; set; }
    }

    public static List<Activity> SelectActivities(List<Activity> activities)
    {
        // Sort by end time
        var sorted = activities
            .OrderBy(a => a.End)
            .ToList();

        var selected = new List<Activity>();

        foreach (var activity in sorted)
        {
            // Check if no overlap with last selected
            if (selected.Count == 0 ||
                selected[selected.Count - 1].End <= activity.Start)
            {
                selected.Add(activity);
            }
        }

        return selected;
    }

    public static void Main()
    {
        var activities = new List<Activity>
        {
            new Activity { Name = "A", Start = 1, End = 3 },
            new Activity { Name = "B", Start = 2, End = 5 },
            new Activity { Name = "C", Start = 4, End = 6 },
            new Activity { Name = "D", Start = 6, End = 9 },
        };

        var result = SelectActivities(activities);

        Console.WriteLine("Selected Activities:");
        foreach (var a in result)
            Console.WriteLine($"{a.Name}: {a.Start}-{a.End}");
    }
}

public class FractionalKnapsack
{
    public class Item
    {
        public string Name { get; set; }
        public double Value { get; set; }
        public double Weight { get; set; }
    }

    public static double MaxValue(List<Item> items, double capacity)
    {
        // Sort by value-to-weight ratio (descending)
        var sorted = items
            .OrderByDescending(x => x.Value / x.Weight)
            .ToList();

        double totalValue = 0;
        double remainingCapacity = capacity;

        foreach (var item in sorted)
        {
            if (remainingCapacity <= 0) break;

            if (item.Weight <= remainingCapacity)
            {
                // Take whole item
                totalValue += item.Value;
                remainingCapacity -= item.Weight;
            }
            else
            {
                // Take fraction of item
                double fraction = remainingCapacity / item.Weight;
                totalValue += fraction * item.Value;
                remainingCapacity = 0;
            }
        }

        return totalValue;
    }

    public static void Main()
    {
        var items = new List<Item>
        {
            new Item { Name = "Gold", Value = 100, Weight = 10 },
            new Item { Name = "Silver", Value = 60, Weight = 20 },
            new Item { Name = "Bronze", Value = 40, Weight = 30 },
        };

        double maxVal = MaxValue(items, 50);
        Console.WriteLine($"Maximum value: {maxVal}");
    }
}

public class HuffmanCoding
{
    public class Node : IComparable<Node>
    {
        public char? Character { get; set; }
        public int Frequency { get; set; }
        public Node Left { get; set; }
        public Node Right { get; set; }

        public int CompareTo(Node other)
        {
            return this.Frequency.CompareTo(other.Frequency);
        }
    }

    public static Dictionary<char, string> BuildHuffmanCodes(string text)
    {
        // Count frequencies
        var freq = new Dictionary<char, int>();
        foreach (char c in text)
        {
            if (freq.ContainsKey(c)) freq[c]++;
            else freq[c] = 1;
        }

        // Build priority queue with leaf nodes
        var pq = new PriorityQueue<Node, int>();
        foreach (var kvp in freq)
        {
            var node = new Node
            {
                Character = kvp.Key,
                Frequency = kvp.Value
            };
            pq.Enqueue(node, node.Frequency);
        }

        // Build tree by merging
        while (pq.Count > 1)
        {
            var left = pq.Dequeue();
            var right = pq.Dequeue();

            var parent = new Node
            {
                Frequency = left.Frequency + right.Frequency,
                Left = left,
                Right = right
            };

            pq.Enqueue(parent, parent.Frequency);
        }

        var root = pq.Dequeue();

        // Generate codes
        var codes = new Dictionary<char, string>();
        GenerateCodes(root, "", codes);

        return codes;
    }

    private static void GenerateCodes(Node node, string code,
        Dictionary<char, string> codes)
    {
        if (node == null) return;

        if (node.Character != null)
            codes[node.Character.Value] = code;

        GenerateCodes(node.Left, code + "0", codes);
        GenerateCodes(node.Right, code + "1", codes);
    }

    public static void Main()
    {
        string text = "hello world";
        var codes = BuildHuffmanCodes(text);

        Console.WriteLine("Huffman Codes:");
        foreach (var kvp in codes.OrderBy(x => x.Value.Length))
            Console.WriteLine($"{kvp.Key}: {kvp.Value}");
    }
}

public class JobSequencing
{
    public class Job
    {
        public string Id { get; set; }
        public int Deadline { get; set; }
        public int Profit { get; set; }
    }

    public static int MaxProfit(List<Job> jobs)
    {
        // Sort by profit (descending)
        var sorted = jobs
            .OrderByDescending(j => j.Profit)
            .ToList();

        int maxDeadline = sorted.Max(j => j.Deadline);
        var slots = new bool[maxDeadline + 1];
        var result = new string[maxDeadline + 1];

        int totalProfit = 0;

        foreach (var job in sorted)
        {
            // Place job in latest available slot before deadline
            for (int i = job.Deadline; i >= 1; i--)
            {
                if (!slots[i])
                {
                    slots[i] = true;
                    result[i] = job.Id;
                    totalProfit += job.Profit;
                    break;
                }
            }
        }

        return totalProfit;
    }

    public static void Main()
    {
        var jobs = new List<Job>
        {
            new Job { Id = "A", Deadline = 4, Profit = 20 },
            new Job { Id = "B", Deadline = 1, Profit = 10 },
            new Job { Id = "C", Deadline = 3, Profit = 40 },
            new Job { Id = "D", Deadline = 2, Profit = 30 },
        };

        int profit = MaxProfit(jobs);
        Console.WriteLine($"Maximum profit: {profit}");
    }
}

public class MinimumPlatforms
{
    public static int FindPlatforms(int[] arrivals, int[] departures)
    {
        // Sort both arrays
        Array.Sort(arrivals);
        Array.Sort(departures);

        int platforms = 0, maxPlatforms = 0;
        int i = 0, j = 0;

        while (i < arrivals.Length && j < departures.Length)
        {
            if (arrivals[i] <= departures[j])
            {
                // Train arrives, need platform
                platforms++;
                maxPlatforms = Math.Max(maxPlatforms, platforms);
                i++;
            }
            else
            {
                // Train departs, free platform
                platforms--;
                j++;
            }
        }

        return maxPlatforms;
    }

    public static void Main()
    {
        int[] arrivals = { 900, 940, 950, 1100, 1500, 1800 };
        int[] departures = { 910, 1200, 1120, 1130, 1900, 2000 };

        int platforms = FindPlatforms(arrivals, departures);
        Console.WriteLine($"Minimum platforms needed: {platforms}");
    }
}